BOJ 33805 Red and Blue

문제 링크입니다.

문제 요약

주어진 $N$개의 점을 잇고 간선이 교차하지 않는 서로 다른 두 스패닝 트리를 찾으세요.

풀이

주어진 점들을 연결하는 두 개의 교차하지 않는 스패닝 트리를 만들어야 합니다. 우선 교차하지 않는 $2N-2$개의 선분을 그리는 데에 집중해 봅시다.

주어진 점 집합의 볼록 껍질 위에 있지 않는 점 $g$를 기준으로 잡읍시다. 셋 이상의 점이 한 직선 위에 있지 않음이 보장되므로, 점 $g$와 나머지 점들을 잇는 $N-1$개의 선분은 서로 교차하지 않습니다.

한편 나머지 $N-1$개의 점을 $g$를 기준으로 각도 정렬해 그 순서대로 잇는 선분을 그리면, 이 선분들 역시 서로 교차하지 않으며 아까 그린 나머지 $N-1$개의 선분과도 교차하지 않습니다.

따라서 이중 적당히 $N-1$개의 선분을 골라 스패닝 트리 하나를 만들고, 나머지 선분들로 스패닝 트리를 또 만들면 문제의 조건에 맞는 답을 구할 수 있습니다. 제 방법은 다음 그림과 같습니다.

모든 점이 볼록 껍질 위에 있는 경우를 생각해 봅시다. 이 경우에는 교차하지 않도록 최대한 많은 선분을 그렸을 때의 결과물이 다각형의 삼각분할 꼴이 되는데, 이를 구성하는 선분은 총 $2N-3$개입니다. 교차하지 않도록 그릴 수 있는 선분 개수가 모자라기 때문에 이 경우에는 스패닝 트리 두 개를 구성할 수 없습니다.

점을 정렬하는 과정을 빼면 나머지는 모두 선형에 해결할 수 있습니다. 따라서 총 시간 복잡도 ${\cal O}(N \lg N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
pll operator-(pll a, pll b){
	return {a.x-b.x, a.y-b.y};
}
inline ll dist(pll a, pll b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(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);
}

map<pll, int> G;

vector<pll> ConvexHull(vector<pll> v){
	sort(v.begin(), v.end());
	if(v.size() <= 2) return v;
	vector<pll> up, down;
	for(auto& p : v){
		while(up.size() >= 2 && ccw(up[up.size()-2], up[up.size()-1], p) >= 0){
			G[up.back()]++;
			up.pop_back();
		}
		up.push_back(p);
		while(down.size() >= 2 && ccw(down[down.size()-2], down[down.size()-1], p) <= 0){
			G[down.back()]++;
			down.pop_back();
		}
		down.push_back(p);
	}
	down.insert(down.end(), up.rbegin()+1, up.rend()-1);
	return down;
}

struct Point{
	pll p; int idx;
};

int get4(pll o, pll p){
	if(o.x-p.x > 0 && o.y-p.y >= 0) return 1;
	if(o.x-p.x <= 0 && o.y-p.y > 0) return 2;
	if(o.x-p.x < 0 && o.y-p.y <= 0) return 3;
	if(o.x-p.x >= 0 && o.y-p.y < 0) return 4;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; vector<pll> p(n);
	for(int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
	auto hull = ConvexHull(p);
	if(hull.size() == n) return !(cout << -1);
	cout << 2*n-2 << '\n';
	pll gizun; for(auto& [key, val] : G) if(val == 2){
		gizun = key; break;
	}
	int gidx;
	for(int i = 0; i < n; i++) if(gizun == p[i]){
		gidx = i; break;
	}
	vector<Point> v;
	for(int i = 0; i < n; i++){
		if(i != gidx) v.push_back({p[i], i+1});
	}
	sort(v.begin(), v.end(), [&](Point& a, Point& b){
		int a4 = get4(p[gidx], a.p), b4 = get4(p[gidx], b.p);
		if(a4 != b4) return a4 < b4;
		return ccw(p[gidx], a.p, b.p) < 0;
	});
	cout << v[0].idx << ' ' << v[1].idx << " R\n";
	for(int i = 1; i < v.size(); i++) cout << gidx+1 << ' ' << v[i].idx << " R\n";
	cout << gidx+1 << ' ' << v[0].idx << " B\n";
	v.push_back(v[0]);
	for(int i = v.size()-2; i; i--) cout << v[i+1].idx << ' ' << v[i].idx << " B\n";
}