BOJ 20939 달고나

문제 링크입니다.

χ

주어진 다각형과 원을 평면 그래프로 바꿔 먹을 수 있습니다. 다각형은 꼭짓점과 모서리를 각각 정점과 간선으로, 원은 적당히 둘레 위에 정점이 있다고 생각하면 됩니다.

단일 연결 요소인 평면 그래프에서, 외부 영역을 제외하면 v-e+f = 1이 성립합니다. 문제에서는 외부 영역을 포함하고 연결 요소가 여러 개일 수 있기 때문에, 결국 구해야 하는 답은

e-v+#component+1임을 알 수 있습니다. #component는 서로 만나는 도형들을 분리 집합 등으로 관리해 주거나, 그냥 BFS 돌아도 됩니다.

도형 연결하기

그래서, 주어진 다각형과 원이 만나는지, 몇 개의 교점을 갖는지 알아내야 합니다. 선분과 원 (단위 도형으로 부를게요.) 의 개수의 합이 2000개 언저리이므로, 모든 단위 도형들의 쌍을 따져봐도 됩니다. 다행히 셋 이상의 단위 도형이 한 점에서 만나는 경우가 없어서, 모든 교점은 서로 다른 위치에 생깁니다. 교점이 생긴다면, 그 점에서 만나는 두 간선이 둘로 쪼개지고 정점이 하나 늘어나는 꼴이므로 실제로는 그냥 영역의 수가 하나 늘어나는 것과 같게 됩니다.

• 선분-선분 간단한 선분 교차 판정을 구현해 주면 됩니다. 선분 끝에서 만난다거나 하는 경우는 없으니 신나게 짜면 됩니다.
• 원-원 두 원의 중심 사이의 거리와 반지름을 이용해 판단할 수 있습니다. 두 원이 멀리 떨어져 있을 때 뿐만 아니라, 한 원이 다른 원을 포함하고 있는 경우에도 교점이 생기지 않을 수 있음에 유의해 주세요.
• 원-선분 직선과 원 사이의 관계와 양 끝 점의 위치를 잘 이용해 케이스를 분류할 수 있습니다. 선분의 끝점이 원의 둘레 위에 있는 경우가 없음에 감사합시다.
  • 양 끝 점이 원 안에 있는 경우 : 교점이 생길 수 없습니다.
  • 한 끝 점만 원 안에 있는 경우 : 반드시 하나의 교점이 생깁니다.
  • 두 끝 점이 모두 원 바깥에 있는 경우 : 원의 중심에서 선분 위에 수선의 발을 내릴 수 있는지를 따지고, 가능하다면 그 거리를 원의 반지름과 비교해서 교점의 수를 구할 수 있습니다.

해서, 이상의 내용을 잘 구현하면 AC를 받을 수 있습니다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using ld = long double;

pll operator- (pll a, pll b){
	return {a.x-b.x, a.y-b.y};
}

inline auto outer(pll a, pll b){
	return a.x*b.y-a.y*b.x;
}
inline auto ccw(pll a, pll b, pll c){
	auto ret = outer(b-a, c-a);
	return (ret<0)-(ret>0);
}
inline auto cccw(pll a, pll b, pll c, pll d){
	d = d-(c-b);
	return ccw(a, b, d);
}
inline void swap(pll* a, pll* b){
	pll c = *a;
	*a = *b;
	*b = c;
}
inline bool intersect(pll a, pll b, pll c, pll d){
	ll line1 = ccw(a, b, c) * ccw(a, b, d);
	ll line2 = ccw(c, d, a) * ccw(c, d, b);
	if(!line1 && !line2){
		if(b<a) swap(a, b);
		if(d<c) swap(c, d);
		return (c <= b && a <= d);
	}
	return line1 <= 0 && line2 <= 0;
}

int par[2020];

int f(int x){
	return par[x] < 0 ? x : par[x] = f(par[x]);
}

void u(int x, int y){
	x = f(x); y = f(y);
	if(x == y) return;
	if(par[x] > par[y]) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

vector<vector<pll>> poly;
ll ans;

void line_line(int a, int b){
	int ret = 0;
	vector<pll>& A = poly[a];
	vector<pll>& B = poly[b];
	for(int i = 1; i < A.size(); i++) for(int j = 1; j < B.size(); j++){
		if(intersect(A[i-1], A[i], B[j-1], B[j])){
			u(a, b);
			ret++;
		}
	}
	ans += ret;
}

void circ_line(int a, int b){
	vector<pll>& A = poly[a];
	vector<pll>& B = poly[b];
	int ret = 0;
	ll x_r = A[1].x, y_r = A[1].y, r = A[0].y;
	for(int i = 1; i < B.size(); i++){
		ll x_1 = B[i-1].x, y_1 = B[i-1].y;
		ll x_2 = B[i].x, y_2 = B[i].y;
		ll x_h = ((y_2-y_1)*(y_2-y_1)*x_1 + (x_2-x_1)*(x_2-x_1)*x_r + (x_2-x_1)*(y_1-y_r)*(y_1-y_2));
		ll y_h = ((x_2-x_1)*(x_2-x_1)*y_1 + (y_2-y_1)*(y_2-y_1)*y_r + (y_2-y_1)*(x_1-x_r)*(x_1-x_2));
		ll ym = min(y_1, y_2), yM = max(y_1, y_2), xm = min(x_1, x_2), xM = max(x_1, x_2);
		ll sqsq = (y_2-y_1)*(y_2-y_1)+(x_2-x_1)*(x_2-x_1);
		bool p1 = ((x_1-x_r)*(x_1-x_r)+(y_1-y_r)*(y_1-y_r) <= r*r);
		bool p2 = ((x_2-x_r)*(x_2-x_r)+(y_2-y_r)*(y_2-y_r) <= r*r);
		if(p1 && p2);
		else if(p1^p2){
			u(a, b); ret++;
		}
		else if(sqsq*ym <= y_h && y_h <= sqsq*yM && sqsq*xm <= x_h && x_h <= sqsq*xM){
			ll delta = sqsq*r*r-((y_2-y_1)*x_r - (x_2-x_1)*y_r + y_1*(x_2-x_1) - x_1*(y_2-y_1))*((y_2-y_1)*x_r - (x_2-x_1)*y_r + y_1*(x_2-x_1) - x_1*(y_2-y_1));
			if(delta >= 0) u(a, b);
			if(delta > 0) ret += 2;
			else if(!delta) ret++;
		}
	}
	ans += ret;
}

void circ_circ(int a, int b){
	int ret = 0;
	if(poly[a][0].y > poly[b][0].y) swap(a, b);
	vector<pll>& A = poly[a];
	vector<pll>& B = poly[b];
	ll x_1 = A[1].x, y_1 = A[1].y, r1 = A[0].y;
	ll x_2 = B[1].x, y_2 = B[1].y, r2 = B[0].y;
	ll d = (x_2-x_1)*(x_2-x_1)+(y_2-y_1)*(y_2-y_1);
	if((r2-r1)*(r2-r1) <= d && d <= (r2+r1)*(r2+r1)){
		u(a, b);
		ret += 1+((r2-r1)*(r2-r1) < d && d < (r2+r1)*(r2+r1));
	}
	ans += ret;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n; memset(par, -1, sizeof(par)); poly.resize(n+1);
	for(int i = 1; i <= n; i++){
		int m; cin >> m;
		if(m == 1){
			ll X, Y, R; cin >> X >> Y >> R;
			poly[i].push_back({1, R});
			poly[i].push_back({X, Y});
		}
		else{
			poly[i].resize(m+1);
			for(int j = 0; j < m; j++) cin >> poly[i][j].x >> poly[i][j].y;
			poly[i][m] = poly[i][0]; 
		}
	}
	ans = 1;
	for(int a = 1; a <= n; a++) for(int b = a+1; b <= n; b++){
		if(poly[a].size() == 2){
			if(poly[b].size() == 2){
				circ_circ(a, b);
			}
			else circ_line(a, b);
		}
		else if(poly[b].size() == 2) circ_line(b, a);
		else line_line(a, b);
		//cout << a << ' ' << b << ' ' << ans << '\n';
	}
	for(int i = 1; i <= n; i++) if(f(i) == i) ans++;
	cout << ans;
}