104292024-04-02 10:53:55szilÚthálózatbővítéscpp17Elfogadva 100/100490ms63908 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva12ms20752 KiB
2Elfogadva136ms33248 KiB
subtask210/10
3Elfogadva9ms23124 KiB
4Elfogadva8ms23088 KiB
5Elfogadva9ms23356 KiB
6Elfogadva9ms23460 KiB
7Elfogadva9ms23576 KiB
subtask320/20
8Elfogadva10ms23620 KiB
9Elfogadva9ms23912 KiB
10Elfogadva12ms24068 KiB
11Elfogadva18ms24992 KiB
12Elfogadva28ms25948 KiB
13Elfogadva119ms33452 KiB
14Elfogadva238ms44004 KiB
15Elfogadva18ms29640 KiB
16Elfogadva41ms34676 KiB
17Elfogadva107ms39328 KiB
subtask410/10
18Elfogadva9ms30684 KiB
19Elfogadva17ms31432 KiB
20Elfogadva14ms31512 KiB
21Elfogadva19ms32800 KiB
22Elfogadva18ms32200 KiB
subtask530/30
23Elfogadva13ms31388 KiB
24Elfogadva28ms33256 KiB
25Elfogadva12ms31620 KiB
26Elfogadva12ms31552 KiB
27Elfogadva20ms32596 KiB
28Elfogadva32ms34036 KiB
29Elfogadva48ms35404 KiB
30Elfogadva25ms34820 KiB
31Elfogadva41ms39232 KiB
32Elfogadva116ms42752 KiB
subtask630/30
33Elfogadva64ms44776 KiB
34Elfogadva35ms39412 KiB
35Elfogadva226ms52824 KiB
36Elfogadva261ms53088 KiB
37Elfogadva266ms53084 KiB
38Elfogadva349ms55992 KiB
39Elfogadva405ms56780 KiB
40Elfogadva490ms58364 KiB
41Elfogadva368ms63908 KiB
42Elfogadva239ms38792 KiB