백준7420 맹독 방벽

작성일 | In

문제 링크

  • http://icpc.me/7420

문제 출처

  • 2001 NEERC D번

사용 알고리즘

  • Convex Hull

시간복잡도

  • O(NlgN)

풀이

주어지는 점들로 일단 볼록껍질을 만들어줍시다.
이런식으로 볼록껍질이 만들어졌다고 합시다.


문제에서 요구하는 것은 볼록껍질의 둘레가 아닌, 볼록껍질에서 L만큼(초록색) 떨어진 노란색과 하늘색의 길이의 합입니다.

노란색의 길이의 합은 볼록껍질의 둘레와 동일합니다. 이제, 부채꼴 형태의 하늘색만 처리해주면 됩니다.


두 초록색 선 사이의 각을 θ라고 한다면, 검은색으로 그려져있는 두 벡터 A, B의 사잇각은 pi-θ가 됩니다.
두 벡터의 사잇각은 벡터의 내적과 acos함수를 이용해 쉽게 구할 수 있습니다.
반지름의 길이가 L이고, 중심각이 θ인 호의 길이는 L*θ라는 것을 이용해 정답을 구할 수 있습니다.

전체 코드

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

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

const double pi = 3.1415926535;

int n; ll l;
vector<p> v, hull;

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;
}

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

ll dot(p a, p b){ //백터 내적
	return a.x*b.x + a.y*b.y;
}

int main(){
	cin >> n >> l; v.resize(n);
	for(int i=0; i<n; i++) scanf("%lld %lld", &v[i].x, &v[i].y);

	swap(v[0], *max_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);
	}

	n = hull.size();
	double ans = 0;

	for(int i=0; i<n; i++){
		p prv = hull[(i+n-1)%n], now = hull[i], nxt = hull[(i+1)%n];
		double dist1 = dist(now, nxt);
		ans += dist1;
		double dist2 = dist(prv, now);

		ll inner = dot({prv.x-now.x, prv.y-now.y}, {nxt.x-now.x, nxt.y-now.y}); //now->prv 벡터와 now->nxt 벡터의 내적
		double theta = acos((double)inner / dist1 / dist2); //사잇각 구하기
		theta = pi- theta; //180 - theta
		ans += l * theta; //호의 길이
	}

	printf("%.0lf", ans);
}