백준10321 요새 건설

작성일 | In

문제 링크

  • http://icpc.me/10321

문제 출처

  • 2014 BAPC C번

사용 알고리즘

  • Convex Hull

시간복잡도

  • O(n2 log n)
  • O(n2)

풀이

주어진 점들을 이용해 삼각형 혹은 사각형의 넓이가 최대가 되기 위해서는 해당 점들이 convex hull 위에 있어야 하는 것은 자명하다.
볼록껍질의 이루는 점들의 개수를 N이라고 하자. 점은 3개 이상 주어지기 때문에, 볼록껍질을 이루는 점의 개수 N은 3보다 작을 수 없다.
N이 3이라면 점 3개로 만들어지는 삼각형의 넓이를 출력하면 된다.
N이 3보다 큰 경우에는 N개의 점들 중에서 4개의 점들 골라 만들 수 있는 사각형 중 가장 넓은 사각형의 넓이를 출력하면 됩니다.

사각형을 찾는 방법은 O(N2lgN)과 O(N2)방법이 있습니다.
기본적인 아이디어는 대각선이 될 점 2개를 고정시키고, 만들어진 대각선 L로 나누어진 두 그룹에서 각각 L과 가장 먼 점을 하나씩 골라주면 됩니다.

N2lgN

대각선 L로 나누어진 두 그룹을 봅시다.

점들을 시계방향 혹은 반시계방향으로 순회하면, 빨간 선과의 길이가 증가하다가 감소하는, Convex Function 형태가 됩니다. 그러므로 삼분 탐색을 적용하면 가능한 O(N2)개의 대각선마다 O(lgN)만에 계산을 하므로 O(N2lgN)이 걸립니다.

N2

대각선 L을 이루는 점 i, j를 봅시다.
i를 고정하고 j를 반시계방향 순서대로 돌렸을 때, 대각선 L에서 가장 먼 점 p, q도 반시계방향으로 이동하기 때문에 p, q는 최대 O(N)번만 이동하게 됩니다. 그러므로 O(N2 + N) = O(N2)만에 풀 수 있습니다.

전체 코드

N2lgN

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
104
105
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;
typedef long long ll;
vector<p> point; //input data
vector<p> ret; //convex hull
int n;

ll ccw(p a, p b){ return (ll)a.x*b.y - (ll)b.x*a.y; }
int ccw(p a, p b, p c){
	ll val = ccw({b.x-a.x, b.y-a.y}, {c.x-a.x, c.y-a.y});
	if(val > 0) return 1;
	if(val < 0) return -1;
	return 0;
}

bool cmp(p a, p b){
	int val = ccw(point[0], a, b);
	if(val > 0) return true;
	if(val < 0) return false;
	if(a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

void graham(){ //graham scan (get convex hull)
	for(int i=0; i<n; i++){
		while(ret.size() >= 2 && ccw(ret[ret.size()-2], ret.back(), point[i]) <= 0) ret.pop_back();
		ret.push_back(point[i]);
	}
}

int area(p a, p b, p c){ //get (triangle area * 2)
	int ret = (a.x*b.y) + (b.x*c.y) + (c.x*a.y);
	ret -= (b.x*a.y) + (c.x*b.y) + (a.x*c.y);
	return abs(ret);
}

int search(int i, int j, int flag){ //get p or q
	if(flag == 1){
		int s = i+1, e = j-1;
		while(s+3 <= e){
			int l = (2*s+e)/3, r = (s+2*e)/3;
			if(area(ret[i], ret[j], ret[l]) < area(ret[i], ret[j], ret[r])) s = l;
			else e = r;
		}
		int ma = 0;
		for(int k=s; k<=e; k++){
			ma = max(ma, area(ret[i], ret[j], ret[k]));
		}
		return ma;
	}

	int s = j+1, e = i-1; if(e < s) e += n;
	while(s+3 <= e){
		int l = (2*s+e)/3, r = (s+2*e)/3;
		if(area(ret[i], ret[j], ret[l%n]) < area(ret[i], ret[j], ret[r%n])) s = l;
		else e = r;
	}

	int ma = 0;
	for(int k=s; k<=e; k++){
		ma = max(ma, area(ret[i], ret[j], ret[k%n]));
	}
	return ma;
}

void f(){
	cin >> n;
	point.resize(n), ret.clear();
	int idx = 0;
	for(int i=0; i<n; i++){
		cin >> point[i].x >> point[i].y;
		if(point[idx].x > point[i].x) idx = i;
		else if(point[idx].x == point[i].x && point[idx].y > point[i].y) idx = i;
	}
	swap(point[idx], point[0]);
	sort(point.begin()+1, point.end(), cmp);
	graham();

	if(ret.size() == 3){
		int val = area(ret[0], ret[1], ret[2]);
		printf("%d%s\n", val/2, val%2 ? ".5" : "");
		return;
	}

	n = ret.size();

	int ans = 0;
	for(int i=0; i<n; i++){
		for(int j=i+2; j<n; j++){
			if(i == 0 && j == n-1) continue;
			ans = max(ans, search(i, j, 1) + search(i, j, 2));
		}
	}
	printf("%d%s\n", ans/2, ans%2 ? ".5" : "");
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int asdf; cin >> asdf;
	while(asdf--) f();
}

N2

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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;
typedef long long ll;
vector<p> point;
vector<p> ret;
int n;

ll ccw(p a, p b){ return (ll)a.x*b.y - (ll)b.x*a.y; }

int ccw(p a, p b, p c){
	ll val = ccw({b.x-a.x, b.y-a.y}, {c.x-a.x, c.y-a.y});
	if(val > 0) return 1;
	if(val < 0) return -1;
	return 0;
}

bool cmp(p a, p b){
	int val = ccw(point[0], a, b);
	if(val > 0) return true;
	if(val < 0) return false;
	if(a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

void graham(){
	for(int i=0; i<n; i++){
		while(ret.size() >= 2 && ccw(ret[ret.size()-2], ret.back(), point[i]) <= 0) ret.pop_back();
		ret.push_back(point[i]);
	}
}

int area(p a, p b, p c){
	int ret = (a.x*b.y) + (b.x*c.y) + (c.x*a.y);
	ret -= (b.x*a.y) + (c.x*b.y) + (a.x*c.y);
	return abs(ret);
}

void f(){
	cin >> n;
	point.resize(n), ret.clear();
	int idx = 0;
	for(int i=0; i<n; i++){
		cin >> point[i].x >> point[i].y;
		if(point[idx].x > point[i].x) idx = i;
		else if(point[idx].x == point[i].x && point[idx].y > point[i].y) idx = i;
	}
	swap(point[idx], point[0]);
	sort(point.begin()+1, point.end(), cmp);
	graham();

	if(ret.size() == 3){
		int val = area(ret[0], ret[1], ret[2]);
		printf("%d%s\n", val/2, val%2 ? ".5" : "");
		return;
	}

	n = ret.size();

	int ans = 0;
	for(int i=0; i<n; i++){
		int p = i+1, q = i+3;
		p %= n, q %= n;
		for(int j=i+2; j<n; j++){
			if(i == 0 && j == n-1) continue;
			while((p+1)%n != j && area(ret[i], ret[j], ret[p]) <= area(ret[i], ret[j], ret[p+1])) p = (p+1)%n;
			while((q+1)%n != i && area(ret[i], ret[j], ret[q]) <= area(ret[i], ret[j], ret[q+1])) q = (q+1)%n;
			int now = area(ret[i], ret[j], ret[p]) + area(ret[i], ret[j], ret[q]);
			ans = max(ans, now);
		}
	}
	printf("%d%s\n", ans/2, ans%2 ? ".5" : "");
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
	int asdf; cin >> asdf;
	while(asdf--) f();
}