백준 13329 Meteor Shower

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

 

다각형이라고 생각하면 너무 무섭다. 다 가려지는지 확인한다에서 스위핑이 생각난다. 다행히 다각형이 모두 단순 볼록하고, 서로 겹치지 않는다.

원점 기준으로 각도정렬한 뒤 스위핑한다고 생각하면, 각 도형을 각도정렬 기준 가장 먼저/나중에 나오는 점을 잇는 선분으로 생각할 수 있다. 

 

선분끼리 상하 관계를 구하면 된다는 점에서 핀볼과 비슷한 접근이지만 원점으로부터 가려지냐? 라는 기준이 핀볼보다 복잡한 만큼 생각을 더 해야 한다. 처음에는 핀볼처럼 리차오를 쓸까? 싶었는데, 비슷한 사고방식으로 쓰면 너무 복잡해질 것 같아서 set 스위핑 쪽으로 생각을 바꿨다.

 

어떤 두 점을 골라도 고른 두 점과 원점이 일직선에 있지 않는다는 조건이 붙으니, 스위핑을 좀 더 편하게 할 수 있다. 이런 류의 스위핑에서 항상 하는 대로 모든 선분의 시작점/끝점을 모아 정렬한 뒤, 순서대로 보며 시작점이면 set에 넣고 끝점이면 뺀다. 하나의 점을 처리한 후 set에 있는 선분 중 원점과 가장 가까운 선분에 체크하고, 모든 점을 처리한 뒤 체크되지 않은 선분의 수를 세면 문제를 풀 수 있다. 원점에서 어떤 선분이 보인다면, 스위핑 중 해당 구간을 처리할 때 해당 선분보다 원점에 더 가까운 선분이 없어야 하니 이러한 풀이는 정당하다. 즉, set에 담긴 선분 중 임의의 두 개를 뽑았을 때 어떤 선분이 더 원점에 가까운지 판별할 수 있는 정렬 기준을 설정하면 문제를 풀 수 있다.

 

스위핑 중이니 set에 담긴 선분끼리는 모두 겹치는 구간이 있다. set에 들어 있는 두 선분 a, b를 비교할 때, 일반성을 잃지 않고 a의 시작점이 b의 시작점보다 각도순으로 먼저 나온다고 가정하자. 이때 (b의 시작점 - 원점) 선분과 선분 a가 겹친다면 a < b, 아니라면 b < a이다. 두 선분의 시작점과 원점이 일직선에 있는 경우는 없으니 cmp(a,a) = false여야 한다는 점만 주의하면 strict weak ordering을 지킬 수 있고, 올바른 정렬 기준이 되어 문제를 풀 수 있다.

 

처음에는 선분 교차를 쓸데없이 엄밀히 짜서 strict weak ordering이 안 맞춰진 탓에 틀렸던 것 같다. 사실 아직 왜틀렸는지모르겟다..

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
struct Point {
    ll x, y;
};
struct Line {
    Point s, e;
    int idx;
};
struct P2{
    Point p;
    int idx, d;
};
 
int ccw(Point a, Point b, Point c) {
    ll ret = a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;
    return (ret > 0) - (ret < 0);
}
 
bool operator<(Point l, Point r) {
    return ccw({0,0}, l, r) < ccw({0,0}, r, l);
}
 
bool intersect(Line a, Line b) {
    int a1 = ccw(a.s, a.e, b.s), a2 = ccw(a.s, a.e, b.e);
    int b1 = ccw(b.s, b.e, a.s), b2 = ccw(b.s, b.e, a.e);
    return a1*a2 == -1 and b1*b2 == -1;
}
 
int chk[101010];
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    int N;
    cin >> N;
    vector<Line> poly;
    vector<P2> points; 
    for (int i = 0, M; i < N; i++){
        cin >> M;
        vector<Point> v(M);
        for (auto&[x,y] : v) cin >> x >> y;
        sort(v.begin(), v.end());
        poly.push_back({v[0], v.back(), i});
        points.push_back({v[0], i, 1});
        points.push_back({v.back(), i, 0});
    }
    auto line_cmp = [&](const Line& a, const Line& b) {
        if (ccw({0,0}, a.s, b.s) == 1) return !intersect(b, {{0,0}, a.s, -1});
        return intersect(a, {{0,0}, b.s, -1});
    };
    set<Line, decltype(line_cmp)> st(line_cmp);
    sort(points.begin(), points.end(), [&](P2 a, P2 b) {
        int c = ccw({0,0}, a.p, b.p);
        if (c) return c < 0;
        return a.d < b.d;
    });
    for (auto p : points){
        if (p.d == 0) st.erase(st.find(poly[p.idx]));
        else st.insert(poly[p.idx]);
        if (st.size()) chk[st.begin()->idx] = 1;
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (!chk[i])
            ans++;
    }
    cout << ans;
}