백준13307 레이저 센서

작성일 | In

문제 링크

  • http://icpc.me/13307

문제 출처

  • 2016 KOI 중등부 4번

사용 알고리즘

  • 분할 정복

시간복잡도

  • $O(N^2 log N)$

풀이

N개의 파란점과 2N개의 빨간점이 주어질 때, 파란점 1개와 빨간점 2개씩 총 N번 매칭하는 문제입니다.
세 점이 연결된 다음에는 영역이 세 부분으로 나뉘게 되는데, 각 영역에서 파란점과 빨간점의 개수가 1:2를 유지해야 합니다. 그러므로 문제를 풀 때 1:2 비율을 유지하면서 분할 정복을 시도해볼 수 있습니다.

convex hull을 만드는 느낌으로 최외각 점 중 파란색 점을 하나 선택합시다. 최외각에 파란색이 없는 경우는 나중에 생각하고, 일단 파란점이 있는 경우만 생각하겠습니다.
다시 한 번, convex hull을 만드는 느낌으로 선택한 점을 기준으로 잡아서 모든 점들을 각도 순으로 정렬을 해줍니다. 그 다음에 순서대로 점들을 보면서 파란점이면 +2, 빨간점이면 -1을 해줍니다.
0에서 -1로 가는 시점과 -1에서 -2로 가는 시점에서 보는 빨간점들과 연결을 해주면, 연결해준 다음에 나눠지는 모든 영역에서 1:2 비율을 유지합니다. 그러므로 분할정복을 해주면서 부분 문제를 해결해주면 됩니다.

최외각에 파란점이 없는 경우에도 비슷하게 +2, -1을 해주면서, 0이 되는 시점에서 보는 점을 기준으로 두 영역으로 나눠주면 1:2를 유지할 수 있습니다. 단, 이 경우에는 점들을 연결을 하지 않습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
struct p{
    ll x, y, color, idx;
    p(){}
    p(ll x, ll y, ll color, ll idx) : x(x), y(y), color(color), idx(idx) {}
    bool operator < (const p &t) const {
        return x*t.y > y*t.x;
    }
    p operator - (p &t){
        return {x - t.x, y - t.y, this->color, this->idx};
    }
};

p pt[3030];
int ans[1010][2];
int n;

void solve(vector<int> &pidx){
	if(pidx.empty()) return;
	vector<p> v;
	for(int i=0; i<pidx.size(); i++){
		v.push_back(pt[pidx[i]]);
		v.back().idx = pidx[i];
	}
	for(int i=1; i<v.size(); i++){
		if(v[0].y > v[i].y || (v[0].y == v[i].y && v[0].x > v[i].x)){
			swap(v[0], v[i]);
		}
	}
	for(int i=v.size()-1; i>=0; i--) v[i] = v[i] - v[0];
	sort(v.begin() + 1, v.end());

	int st = -1, fst = v[0].idx;
	v.erase(v.begin());

	if(pt[fst].color) st = fst;
	else if(pt[v[0].idx].color) st = v[0].idx;
	else if(pt[v.back().idx].color) st = v.back().idx;

	if(st != -1){
		if(st != fst){
			v.clear();
			for(int i=0; i<pidx.size(); i++){
                if(pidx[i] != st){
				    v.push_back(pt[pidx[i]] - pt[st]);
				    v.back().idx = pidx[i];
                }
			}
			sort(v.begin(), v.end());
		}
		int cnt = 0, pv = -1;
		vector<int> nxt;
		for(int i=0; i<v.size(); i++){
			cnt += pt[v[i].idx].color ? 2 : -1;
			if(cnt == pv){
				if(pv == -1) ans[st][0] = v[i].idx;
                else ans[st][1] = v[i].idx;
				solve(nxt); nxt.clear(); pv--;
				if(pv < -2) pv = 1e9+7;
			}
			else{
				nxt.push_back(v[i].idx);
			}
		}
		solve(nxt); return;
	}

	for(int asdf=0; asdf<2; asdf++){
		int cnt = 0;
		vector<int> nxt;
		for(int i=0; i<v.size(); i++){
			cnt += pt[v[i].idx].color ? 2 : -1;
			nxt.push_back(v[i].idx);
			if(cnt == 0){
				solve(nxt);
				nxt.clear();
				for(int j=i+1; j<v.size(); j++) nxt.push_back(v[j].idx);
				nxt.push_back(fst);
				solve(nxt);
				return;
			}
		}
		reverse(v.begin(), v.end()); //한 방향으로만 탐색하면 분할할 지점을 못 찾을 수 있음
	}
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vector<int> v;
    for(int i=0; i<3*n; i++){
        cin >> pt[i].x >> pt[i].y;
        if(i < n) pt[i].color = 1; //blue
        else pt[i].color = 0; //red
        pt[i].idx = i;
        v.push_back(i);
    }
    solve(v);
    for(int i=0; i<n; i++) cout << ans[i][0]-n+1 << " " << ans[i][1]-n+1 << "\n";
}