백준13310 먼 별

작성일 | In

문제 링크

  • http://icpc.me/13310

문제 출처

  • 2016 전국 본선 고등부4

사용 알고리즘

  • Convex Hull
  • Rotating Calipers

시간복잡도

  • O(log T * N log N)

풀이

N개의 별 중, 가장 거리가 먼 두 쌍을 찾는 방법을 먼저 알아봅시다.
가장 간단한 방법으로는 N2으로 전체 별을 완전 탐색 하는 방법이 있습니다.
아니면 N log N만에 Convex Hull을 구하고, N만에 Rotating Calipers를 돌리는 방법이 있습니다. 이 문제에서는 후자의 방법을 요구합니다.

N개의 별 중 가장 먼 두 쌍을 찾는 것은 Rotating Calipers로 구현을 한다고 합시다. 이제 T+1개의 사진 중, Rotating Calipers로 구한 거리가 가장 짧은 순간을 구해야 합니다.
만약 k라는 지점에서 가장 짧다면, 아래 그래프와 비슷한 형태로 그래프가 그려지게 됩니다.

삼분탐색을 통해 log T번의 시도로 구할 수 있습니다.

그러므로 전체 시간 복잡도는 O(logT * NlogN)입니다.

전체 코드

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

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

struct Star{
	ll x, y, dx, dy;
	void get(){
		cin >> x >> y >> dx >> dy;
	}
};

int n, t;
vector<Star> v;
vector<p> arr;

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

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

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

ll f(ll t){ //ternary search
	for(int i=0; i<n; i++){
		arr[i] = {v[i].x + v[i].dx*t, v[i].y + v[i].dy*t};
	}
	swap(arr[0], *min_element(arr.begin(), arr.end()));
	sort(arr.begin()+1, arr.end(), [](p a, p b){
		int cw = ccw(arr[0], a, b);
		if(cw) return cw > 0;
		return dist(arr[0], a) < dist(arr[0], b);
	});

	//get convx hull
	vector<p> hull;
	for(int i=0; i<n; i++){
		while(hull.size() >= 2 && ccw(hull[hull.size()-2], hull.back(), arr[i]) <= 0){
			hull.pop_back();
		}
		hull.push_back(arr[i]);
	}

	//rotating calipers
	ll ret = 0;
	int p = 0;

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

	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> t;
	v.resize(n), arr.resize(n);
	for(int i=0; i<n; i++) v[i].get();

	//ternary search
	ll s = 0, e = t;
	while(s+3 <= e){
		ll l = (s+s+e)/3, r = (s+e+e)/3;
		if(f(l) > f(r)) s = l;
		else e = r;
	}

	ll ans = 1e18;
	int idx = s;
	for(ll i=s; i<=e; i++){
		ll now = f(i);
		if(ans > now){
			ans = now;
			idx = i;
		}
	}
	cout << idx << "\n" << ans;
}