[BOJ] 13329 Meteor Shower

문제 요약

y>0인 반평면에 다각형들이 있다. 원점에서부터 빛을 쏴서 다각형들을 관측할 때, 어떻게 빛을 쏴도 관측할 수 없는 다각형의 개수를 세서 출력한다.

문제 풀이

이런 류의 문제에서 항상 쓰는 테크닉인 스위핑을 갖고 옵시다. 다만 평소에 쓰는 라인 스위핑이 아닌, 각도 기준으로 스위핑을 진행해야 합니다. 다각형끼리 서로 교차하지 않으므로, 각 다각형을 각도가 가장 작은 점과 각도가 가장 큰 점을 이어주는 선분으로 바꿔줘도 답에는 영향이 없습니다. 그렇다면 문제는 n개의 선분이 주어졌을 때 완전히 가려지는 선분을 구하는 문제로 환원됩니다.

모든 선분의 끝 점을 각도 순으로 정렬합니다. (https://koosaga.com/97) 선분의 시작 지점이 들어올 때 집합에 선분을 추가하고, 종료 지점이 들어올 때 집합에서 선분을 제거합니다. 문제는 변화가 있을 때 마다 현재 각도에서 가장 앞에 있는, 즉 빛을 받는 선분을 구하는 점입니다. 이를 위해 선분들의 정렬 기준을 세워야 합니다. 집합에 들어 있는 원소들은 스위핑 중이니 당연히 한 쪽이 다른 한 쪽에 완전히 포함되거나, 서로 걸쳐 있게 됩니다. (겹치는 각도 영역이 존재하지 않는 경우는 없습니다.) 따라서 이를 CCW를 이용해 두 선분의 겹치는 각도 영역에서 누가 원점과 가까이 있고, 누가 그렇지 않은지를 정렬 기준으로 하여 set을 이용하면 됩니다. 자세한 구현은 코드를 참조하세요.

코드

#pragma GCC optimize("O3")

#include <bits/stdc++.h>
#define x first
#define y second
#define pi make_pair

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pt;

pt read_pt() {
	ll t1, t2;
	cin >> t1 >> t2;
	return make_pair(t1, t2);
}

int ccw(pt a, pt b, pt c) {
	ll t = 1LL * a.x * (b.y - c.y) + 1LL * b.x * (c.y - a.y) + 1LL * c.x * (a.y - b.y);
	return t ? (t > 0 ? 1 : -1) : 0;
}

ll hypot(pt t) {
	return t.x*t.x + t.y*t.y;
}

int check[100005];
pt st[100005], en[100005]; //각 선분의 시점, 종점
int si[100005], ei[100005]; //정렬된 벡터 V에서 각 선분의 시점과 종점이 나타나는 인덱스
vector<pair<pt, int> > V; //스위핑용 벡터, 점/선분 번호

bool compare(pt a, pt b) {
	if ((pi(a.x, a.y) > pi(0LL, 0LL)) ^ (pi(b.x, b.y) > pi(0LL, 0LL))) return pi(a.x, a.y) > pi(b.x, b.y);
	if (ccw(pi(0, 0), a, b) != 0) return ccw(pi(0, 0), a, b) > 0;
	return hypot(a) < hypot(b);
}

struct pn {
	int t;
	bool operator<(const pn &ot) const {
		int a = t, b = ot.t;
		if (a == b) return false;

		if (si[a] <= si[b] && ei[b] <= ei[a]) return ccw(st[a], en[a], st[b]) > 0; //완전히 포함하는 경우
		else if (si[b] <= si[a] && ei[a] <= ei[b]) return ccw(st[b], en[b], st[a]) < 0;

		if (si[a] < si[b]) return ccw(st[a], en[a], st[b]) > 0; //엇갈리는 경우
		else return ccw(st[b], en[b], st[a]) < 0;
	}
};


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		vector<pt> vt; int k; cin >> k;
		for (int j = 1; j <= k; j++) vt.push_back(read_pt());
		pt p1 = *max_element(vt.begin(), vt.end(), compare); //각도 최소 (compare 함수가 +x부터 -x 방향이라 반전했습니다)
		pt p2 = *min_element(vt.begin(), vt.end(), compare); //각도 최대
		V.emplace_back(p1, i);
		V.emplace_back(p2, -i);
		st[i] = p1, en[i] = p2;
	}
	sort(V.begin(), V.end(), [&](pair<pt, int> a, pair<pt, int> b) { // 각도 순서대로 정렬 
		return compare(a.x, b.x);
	});
	reverse(V.begin(), V.end()); // compare 함수가 +x부터 -x 방향이라 반전했습니다
	for (int i = 0; i < V.size(); i++) {
		auto hr = V[i];
		if (hr.y > 0) si[hr.y] = i;
		else ei[-hr.y] = i;
	}

	set<pn> S;
	for (int i = 0; i < V.size(); i++) {
		auto hr = V[i];
		if (hr.y > 0) {
			S.insert({ hr.y });
			auto tmp = *S.begin();
			check[tmp.t] = 1;
		}
		else {
			S.erase({ -hr.y });
			if (S.empty()) continue;
			auto tmp = *S.begin();
			check[tmp.t] = 1;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans += check[i];
	cout << n - ans;
}