1310 2022. 04. 18 20:45:10 Valaki2 Házak cpp14 Elfogadva 100/100 148ms 35948 KiB
#include <bits/stdc++.h>
using namespace std;

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

struct Point {
    int x, y;
    Point() : x(0), y(0) {}
    Point(int x_, int y_) : x(x_), y(y_) {}
};

struct House {
    Point a, b;
    int id;
    House() : a(), b(), id(-1) {}
    House(Point a_, Point b_, int id_) : a(a_), b(b_), id(id_) {}
};

struct Event {
    // -1: kivenni
    // 1: berakni
    Point where;
    int id, type;
    Event() : where(), id(-1), type(0) {}
    Event(Point where_, int id_, int type_)
        : where(where_), id(id_), type(type_) {}
};

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

int direction(Point a, Point b, Point c) {
    return sg((b.y - a.y) * (c.x - a.x) - (c.y - a.y) * (b.x - a.x));
}

bool between(Point a, Point b, Point c) {
    return (c.x >= min(a.x, b.x)) && (c.x <= max(a.x, b.x)) && (c.y >= min(a.y, b.y)) && (c.y <= max(a.y, b.y));
}

Point origo;

bool polarsort(Event a, Event b) {
    int dir = direction(origo, a.where, b.where);
    if(dir == -1) {
        return false;
    }
    if(dir == 1) {
        return true;
    }
    return between(origo, b.where, a.where);
}

int n;
vector<House> houses;
vector<Event> events;

struct msort {
    bool operator()(const House &a, const House &b) const {
        return (direction(a.a, a.b, b.a) == -1 && direction(a.a, a.b, b.b) == -1)
            || (direction(b.a, b.b, a.a) == 1 && direction(b.a, b.b, a.b) == 1);
    }
};

multiset<House, msort> m;
vector<bool> ans;

void add(House h) {
    m.insert(h);
}

void rem(House h) {
    m.erase(m.find(h));
}

void query() {
    if(m.empty()) {
        return;
    }
    House h = *m.begin();
    ans[h.id] = true;
}

void solve() {
    origo = Point(0, 0);
    cin >> n;
    houses.assign(n, House(Point(), Point(), -1));
    for(int i = 0; i < n; i++) {
        cin >> houses[i].a.x >> houses[i].b.y >> houses[i].b.x >> houses[i].a.y;
        houses[i].id = i;
        events.pb(Event(houses[i].a, houses[i].id, 1));
        events.pb(Event(houses[i].b, houses[i].id, -1));
    }
    sort(events.begin(), events.end(), polarsort);
    ans.assign(n, false);
    for(int i = 0; i < (int) events.size(); i++) {
        if(events[i].type == -1) {
            rem(houses[events[i].id]);
        } else {
            add(houses[events[i].id]);
        }
        if(i + 1 != (int) events.size()) {
            if(direction(origo, events[i].where, events[i + 1].where) != 0) {
                query();
            }
        }
    }
    int ans_cnt = 0;
    for(int i = 0; i < n; i++) {
        if(ans[i]) {
            ans_cnt++;
        }
    }
    cout << ans_cnt << "\n";
    for(int i = 0; i < n; i++) {
        if(ans[i]) {
            cout << i + 1 << " ";
        }
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 2ms 1860 KiB
2 Elfogadva 14ms 4984 KiB
subtask2 15/15
3 Elfogadva 1ms 2224 KiB
4 Elfogadva 2ms 2560 KiB
5 Elfogadva 7ms 3864 KiB
6 Elfogadva 13ms 5432 KiB
7 Elfogadva 13ms 5772 KiB
subtask3 15/15
8 Elfogadva 1ms 2956 KiB
9 Elfogadva 1ms 2980 KiB
10 Elfogadva 2ms 3036 KiB
11 Elfogadva 2ms 3072 KiB
12 Elfogadva 2ms 3296 KiB
subtask4 20/20
13 Elfogadva 2ms 3332 KiB
14 Elfogadva 3ms 3668 KiB
15 Elfogadva 8ms 4816 KiB
16 Elfogadva 9ms 5264 KiB
17 Elfogadva 9ms 5468 KiB
subtask5 50/50
18 Elfogadva 27ms 9752 KiB
19 Elfogadva 39ms 11284 KiB
20 Elfogadva 68ms 18288 KiB
21 Elfogadva 143ms 32776 KiB
22 Elfogadva 148ms 35948 KiB