백준9240 로버트 후드

작성일 | In

문제 링크

  • http://icpc.me/9240

문제 출처

  • 2013 NCPC D번

사용 알고리즘

  • Convex Hull
  • Rotating Calipers

시간복잡도

  • O(n log n)

풀이

그냥 rotating calipers만 구현해주면 되는 문제입니다.
그러나 문제의 조건을 이용한다면 rotating calipers를 이용하지 않아도 문제를 풀 수 있습니다.

좌표의 범위는 -1000 ~ 1000입니다. 해당 범위 내에서 convex hull을 만들면 아무리 많아도 껍질 위에 10,000보다 훨씬 적은 양의 점만 있게 됩니다.
그러므로 convex hull을 구한 뒤, 해당 점들에 대해 완전 탐색을 해줘도 되기는 합니다.

전체 코드

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

struct pos{
	int x, y;
	pos(int a, int b) : x(a), y(b) {}
	pos() {}
	bool operator < (pos &rhs){
		if(x != rhs.x) return x < rhs.x;
		return y < rhs.y;
	}
};

vector<pos> point;

int ccw(pos a, pos b, pos c){
	long long 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;
	if(ret > 0) return 1;
	if(ret) return -1;
	return 0;
}

bool chk(pos a, pos b, pos c, pos d){
	pos t = {b.x - a.x, b.y - a.y};
	pos tt = {d.x - c.x, d.y - c.y};
	return ccw({0, 0}, t, tt) >= 0;
}

long long dist(pos a, pos b){
	long long dx = b.x - a.x;
	long long dy = b.y - a.y;
	return dx*dx + dy*dy;
}

double rotatingCalipers(){
	vector<pos> hull;
	swap(point[0], *min_element(point.begin(), point.end()));
	sort(point.begin()+1, point.end(), [](pos a, pos b){
		int cw = ccw(point[0], a, b);
		if(cw) return cw > 0;
		return dist(point[0], a) < dist(point[0], b);
	});
	for(auto i : point){
		while(hull.size() >= 2 && ccw(hull[hull.size()-2], hull.back(), i) <= 0){
			hull.pop_back();
		}
		hull.push_back(i);
	}

	int pt = 0;
	long long ret = 0;
	for(int i=0; i<hull.size(); i++){
		while(pt+1 < hull.size() && chk(hull[i], hull[i+1], hull[pt], hull[pt+1])){
			ret = max(ret, dist(hull[i], hull[pt])); ++pt;
		}
		ret = max(ret, dist(hull[i], hull[pt]));
	}

	return sqrt(ret);
}

int main(){
	int n; cin >> n;
	point.resize(n);
	for(int i=0; i<n; i++){
		scanf("%d %d", &point[i].x, &point[i].y);
	}
	printf("%lf", rotatingCalipers());
}