백준10254 고속도로

작성일 | In

문제 링크

  • http://icpc.me/10254

문제 출처

  • 2014 ACM-ICPC 대전 인터넷 예선 E번

사용 알고리즘

  • Rotating Calipers

시간복잡도

  • O(NlgN)

풀이

Rotating Calipers 구현 문제입니다.
최대 거리가 갱신될 때 정답이 되는 두 점을 같이 갱신하면 됩니다.

전체 코드

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

typedef long long ll;
typedef pair<ll, ll> p;

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

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

bool chk(p s, p e, p ss, p ee){
	p t = {e.x - s.x, e.y - s.y};
	p tt = {ee.x - ss.x, ee.y - ss.y};
	return ccw({0, 0}, t, tt) >= 0;
}

p xx, yy;
vector<p> v, hull;

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

	ll ret = 0;
	int pt = 0;
	for(int i=0; i<hull.size(); i++){
		ll now;
		while(pt+1 < hull.size() && chk(hull[i], hull[i+1], hull[pt], hull[pt+1])){
			now = dist(hull[i], hull[pt]);
			if(now > ret){
				ret = now;
				xx = hull[i];
				yy = hull[pt];
			}
			pt++;
		}
		now = dist(hull[i], hull[pt]);
		if(now > ret){
			ret = now;
			xx = hull[i];
			yy = hull[pt];
		}
	}
}

void solve(){
	v.clear(); hull.clear();
	int n; cin >> n; v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i].x >> v[i].y;
	rot();
	cout << xx.x << " " << xx.y << " " << yy.x << " " << yy.y << "\n";
}

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