9244번: 핀볼

https://www.acmicpc.net/problem/9244

#include<cstdio>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, x0, ck[MXN + 1];
struct st1 {
    int x1, y1, x2, y2, idx;
    bool operator<(st1 i) const {
        int x = max(x1, i.x1);
        return (double)(y2 - y1) / (x2 - x1)*(x - x1) + y1
            < (double)(i.y2 - i.y1) / (i.x2 - i.x1)*(x - i.x1) + i.y1;
    }
}s[MXN];
struct st2 {
    int x, idx, t;
}p[MXN * 2];
set<st1> st;
vector<int> adj[MXN + 1];
void f(int h) {
    if (ck[h]) return;
    ck[h] = 1;
    for (auto it : adj[h]) f(it);
    if (h < n && x0 >= s[h].x1&&x0 <= s[h].x2) x0 = s[h].y1 < s[h].y2 ? s[h].x1 : s[h].x2;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &s[i].x1, &s[i].y1, &s[i].x2, &s[i].y2);
        if (s[i].x1 > s[i].x2) {
            swap(s[i].x1, s[i].x2);
            swap(s[i].y1, s[i].y2);
        }
        s[i].idx = i;
        p[i] = { s[i].x1,i,0 };
        p[i + n] = { s[i].x2,i,1 };
    }
    scanf("%d", &x0);
    sort(p, p + 2 * n, [](st2 i, st2 j) {return i.x < j.x; });
    for (int i = 1, j = 0; i <= 2 * n; i++) if (i == 2 * n || p[i].x^p[j].x) {
        for (int k = j; k < i; k++) if (!p[k].t) st.insert(s[p[k].idx]);
        for (int k = j; k < i; k++) if (p[k].t) {
            auto it1 = st.find(s[p[k].idx]), it2 = it1;
            if (it1 == st.begin()) adj[n].push_back(p[k].idx);
            else adj[(--it1)->idx].push_back(p[k].idx);
            if (++it2 != st.end()) adj[p[k].idx].push_back(it2->idx);
        }
        for (; j < i; j++) if (p[j].t) st.erase(s[p[j].idx]);
    }
    f(n);
    printf("%d", x0);
    return 0;
}