10429 2024. 04. 02 10:53:55 szil Úthálózatbővítés cpp17 Elfogadva 100/100 490ms 63908 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Point {
    ll x, y;

    bool operator==(const Point &p) {
        return x == p.x && y == p.y;
    }
};

struct Line {
    int u, v;
};

ll cross(Point p, Point q) {
    return p.x * q.y - p.y * q.x;
}

ll squared(Point p) {
    return p.x*p.x+p.y*p.y;
}

ll forog(Point a, Point b, Point c) {
    b.x -= a.x; c.x -= a.x;
    b.y -= a.y; c.y -= a.y;
    ll o = cross(b, c);
    if (o > 0) return 1;
    if (o == 0) return 0;
    if (o < 0) return -1;
}

bool operator<(const Point &p, const Point &q) {
    if ((p.x >= 0) == (q.x >= 0)) {
        ll o = cross(p, q);
        if (o == 0) return squared(p) < squared(q);
        return cross(p, q) > 0;
    }
    return (p.x >= 0) < (q.x >= 0);
}

const int MAXN = 200'001;

Point points[MAXN];
Line lines[MAXN];
bool ans[MAXN];
vector<Line> to_remove[MAXN], to_add[MAXN];
set<Line> s;
int n, ox, oy;

bool operator<(const Line &a, const Line &b) {
    Point p1 = points[a.u], q1 = points[a.v], p2 = points[b.u], q2 = points[b.v];
    if (cross(p1, q1) < 0) swap(p1, q1);
    if (cross(p2, q2) < 0) swap(p2, q2);
    if (forog(p1, q1, p2) == 0) {
        return forog(p1, q1, q2) < 0;
    }
    if (forog(p1, q1, q2) == 0) {
        return forog(p1, q1, p2) < 0;
    }
    if (forog(p1, q1, p2) == forog(p1, q1, q2)) return forog(p1, q1, p2) < 0;
    if (forog(p2, q2, p1) == forog(p2, q2, q1)) return forog(p2, q2, p1) > 0;
    throw 1;
}

void solve() {
    vector<int> indices(n);
    iota(indices.begin(), indices.end(), 1);
    sort(indices.begin(), indices.end(), [&](int i, int j){
        return points[i] < points[j];
    });
    for (int i = 0; i < n; ) {
        int j = i;
        while (j + 1 < n && cross(points[indices[i]], points[indices[j + 1]]) == 0) j++;
        for (int k = i; k <= j; k++) {
            for (Line l : to_remove[indices[k]]) {
                s.erase(l);
            }
        }
        if (indices[i] == 300) {
            auto [u, v] = *s.begin();
        }
        if (s.lower_bound({indices[i], indices[i]}) == s.begin()) {
            ans[indices[i]] = true;
        }
        for (int k = i; k <= j; k++) {
            for (Line l : to_add[indices[k]]) {
                s.insert(l);
            }
        }
        i = j + 1;
    }    
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> ox >> oy;
    for (int i = 1; i <= n; i++) {
        cin >> points[i].x >> points[i].y;
        points[i].x -= ox;
        points[i].y -= oy;
    }
    for (int i = 0; i < n-1; i++) {
        int &u = lines[i].u, &v = lines[i].v;
        cin >> u >> v;
        if (points[v] < points[u]) swap(u, v);

        ll o = cross(points[u], points[v]);
        if (o > 0) {
            to_add[u].emplace_back(lines[i]);
            to_remove[v].emplace_back(lines[i]);
        } else if (o < 0) {
            s.insert(lines[i]);
            to_remove[u].emplace_back(lines[i]);
            to_add[v].emplace_back(lines[i]);
        }
    }
    solve();
    cout << count(ans+1, ans+n+1, true) << "\n";
    for (int i = 1; i <= n; i++) {
        if (ans[i]) cout << i << " ";
    }
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 12ms 20752 KiB
2 Elfogadva 136ms 33248 KiB
subtask2 10/10
3 Elfogadva 9ms 23124 KiB
4 Elfogadva 8ms 23088 KiB
5 Elfogadva 9ms 23356 KiB
6 Elfogadva 9ms 23460 KiB
7 Elfogadva 9ms 23576 KiB
subtask3 20/20
8 Elfogadva 10ms 23620 KiB
9 Elfogadva 9ms 23912 KiB
10 Elfogadva 12ms 24068 KiB
11 Elfogadva 18ms 24992 KiB
12 Elfogadva 28ms 25948 KiB
13 Elfogadva 119ms 33452 KiB
14 Elfogadva 238ms 44004 KiB
15 Elfogadva 18ms 29640 KiB
16 Elfogadva 41ms 34676 KiB
17 Elfogadva 107ms 39328 KiB
subtask4 10/10
18 Elfogadva 9ms 30684 KiB
19 Elfogadva 17ms 31432 KiB
20 Elfogadva 14ms 31512 KiB
21 Elfogadva 19ms 32800 KiB
22 Elfogadva 18ms 32200 KiB
subtask5 30/30
23 Elfogadva 13ms 31388 KiB
24 Elfogadva 28ms 33256 KiB
25 Elfogadva 12ms 31620 KiB
26 Elfogadva 12ms 31552 KiB
27 Elfogadva 20ms 32596 KiB
28 Elfogadva 32ms 34036 KiB
29 Elfogadva 48ms 35404 KiB
30 Elfogadva 25ms 34820 KiB
31 Elfogadva 41ms 39232 KiB
32 Elfogadva 116ms 42752 KiB
subtask6 30/30
33 Elfogadva 64ms 44776 KiB
34 Elfogadva 35ms 39412 KiB
35 Elfogadva 226ms 52824 KiB
36 Elfogadva 261ms 53088 KiB
37 Elfogadva 266ms 53084 KiB
38 Elfogadva 349ms 55992 KiB
39 Elfogadva 405ms 56780 KiB
40 Elfogadva 490ms 58364 KiB
41 Elfogadva 368ms 63908 KiB
42 Elfogadva 239ms 38792 KiB