문제 요약
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;
}
'Problem Solving > 문제풀이' 카테고리의 다른 글
[BOJ] 16910 mex와 쿼리 (1) | 2020.03.22 |
---|---|
[BOJ] 14591 KUBC League, 17165 Gosu (0) | 2020.03.22 |
[ICPC] ICL 2016 (GP of Tatarstan) 후기 & 잡설들 (0) | 2020.01.31 |
[BOJ] 10264 Particle Swapping (0) | 2020.01.24 |
[BOJ] 1396 크루스칼의 공 (0) | 2020.01.24 |