10426 2024. 04. 02 10:43:46 szil Úthálózatbővítés cpp17 Elfogadva 100/100 490ms 63912 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] == 221) {
            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 9ms 20908 KiB
2 Elfogadva 128ms 33264 KiB
subtask2 10/10
3 Elfogadva 8ms 23052 KiB
4 Elfogadva 8ms 23120 KiB
5 Elfogadva 9ms 23332 KiB
6 Elfogadva 9ms 23556 KiB
7 Elfogadva 9ms 23676 KiB
subtask3 20/20
8 Elfogadva 8ms 23500 KiB
9 Elfogadva 8ms 23540 KiB
10 Elfogadva 10ms 23720 KiB
11 Elfogadva 17ms 24448 KiB
12 Elfogadva 28ms 25712 KiB
13 Elfogadva 115ms 33296 KiB
14 Elfogadva 239ms 43828 KiB
15 Elfogadva 18ms 29468 KiB
16 Elfogadva 41ms 34516 KiB
17 Elfogadva 101ms 39092 KiB
subtask4 10/10
18 Elfogadva 8ms 30264 KiB
19 Elfogadva 14ms 30972 KiB
20 Elfogadva 14ms 30948 KiB
21 Elfogadva 19ms 32384 KiB
22 Elfogadva 18ms 31848 KiB
subtask5 30/30
23 Elfogadva 10ms 30980 KiB
24 Elfogadva 26ms 32756 KiB
25 Elfogadva 9ms 31028 KiB
26 Elfogadva 9ms 31048 KiB
27 Elfogadva 18ms 32280 KiB
28 Elfogadva 30ms 33676 KiB
29 Elfogadva 46ms 34980 KiB
30 Elfogadva 24ms 34128 KiB
31 Elfogadva 41ms 38572 KiB
32 Elfogadva 116ms 42252 KiB
subtask6 30/30
33 Elfogadva 64ms 44232 KiB
34 Elfogadva 35ms 38832 KiB
35 Elfogadva 226ms 52820 KiB
36 Elfogadva 263ms 53088 KiB
37 Elfogadva 261ms 53084 KiB
38 Elfogadva 349ms 55992 KiB
39 Elfogadva 377ms 56784 KiB
40 Elfogadva 490ms 58364 KiB
41 Elfogadva 379ms 63912 KiB
42 Elfogadva 254ms 38892 KiB