12892022-03-30 13:27:00Valaki2Házakcpp14Wrong answer 0/100194ms27156 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

struct house {
    int x1, y1, x2, y2;
    int id;
    house() : x1(0), y1(0), x2(0), y2(0) {}
};

struct point {
    int x, y;
    int id;
    point() : x(0), y(0), id(-1) {}
    point(int x_, int y_, int id_) : x(x_), y(y_), id(id_) {}
};

struct data {
    int x, y;
    int id;
    data() : x(0), y(0), id(-1) {}
    data(int x_, int y_, int id_) : x(x_), y(y_), id(id_) {}
    bool operator<(const data &other) const {
        if(x + y == other.x + other.y) {
            return id < other.id;
        }
        return x + y < other.x + other.y;
    }
    bool operator>(const data &other) const {
        if(x + y == other.x + other.y) {
            return id > other.id;
        }
        return x + y > other.x + other.y;
    }
    bool operator==(const data &other) const {
        return x == other.x && y == other.y && id == other.id;
    }
    bool operator<=(const data &other) const {
        return !((*this) > other);
    }
    bool operator>=(const data &other) const {
        return !((*this) < other);
    }
};

const point origo = point(0, 0, -1);

int n;
vector<house> v;
vector<point> pts;
vector<int> ans;

int sig(int x) {
    if(x > 0) {
        return 1;
    }
    if(x < 0) {
        return -1;
    }
    return 0;
}

int direction(point a, point b, point c) {
    // right=1, mid=0, left=-1
    // (b.y/b.x)-(c.y/c.x)>0
    // (b.y*c.x)-(c.y*b.x)>0
    // ((b.y-a.y)*(c.x-a.x))-((c.y-a.y)*(b.x-a.x))>0
    return sig(((b.y-a.y)*(c.x-a.x))-((c.y-a.y)*(b.x-a.x)));
}

bool polarsort(point a, point b) {
    int dir = direction(origo, a, b);
    if(dir == 0) {
        return a.x < b.x;
    }
    if(dir == 1) {
        return false;
    } else {
        return true;
    }
}

multiset<data> cur_pts;
vector<bool> in_use;
vector<bool> is_ans;

void add_rem(point p) {
    data d = data(v[p.id].x1, v[p.id].y1, p.id);
    if(in_use[d.id]) {
        in_use[d.id] = false;
        cur_pts.erase(cur_pts.find(d));
    } else {
        in_use[d.id] = true;
        cur_pts.insert(d);
    }
}

void query() {
    data d = *(cur_pts.begin());
    is_ans[d.id] = true;
}

void solve() {
    cin >> n;
    v.assign(n, house());
    for(int i = 0; i < n; i++) {
        cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2;
        v[i].id = i;
        pts.pb(point(v[i].x1, v[i].y2, i));
        pts.pb(point(v[i].x2, v[i].y1, i));
    }
    sort(pts.begin(), pts.end(), polarsort);
    in_use.assign(n, false);
    is_ans.assign(n, false);
    for(int i = 0; i < (int) pts.size(); i++) {
        add_rem(pts[i]);
        if(i + 1 < (int) pts.size()) {
            if(direction(origo, pts[i], pts[i + 1])) {
                query();
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(is_ans[i]) {
            ans.pb(i);
        }
    }
    cout << (int) ans.size() << "\n";
    for(int x : ans) {
        cout << x + 1 << " ";
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms1820 KiB
2Wrong answer13ms3480 KiB
subtask20/15
3Accepted1ms2152 KiB
4Wrong answer2ms2220 KiB
5Wrong answer7ms3004 KiB
6Wrong answer10ms3936 KiB
7Wrong answer14ms4264 KiB
subtask30/15
8Accepted1ms2892 KiB
9Wrong answer1ms2912 KiB
10Wrong answer2ms2936 KiB
11Wrong answer1ms2960 KiB
12Wrong answer3ms3136 KiB
subtask40/20
13Accepted2ms3036 KiB
14Wrong answer3ms3252 KiB
15Wrong answer7ms3944 KiB
16Wrong answer9ms4272 KiB
17Wrong answer9ms4492 KiB
subtask50/50
18Wrong answer20ms6640 KiB
19Wrong answer34ms7680 KiB
20Wrong answer75ms11728 KiB
21Wrong answer187ms24056 KiB
22Wrong answer194ms27156 KiB