문제 링크
- http://icpc.me/7420
문제 출처
- 2001 NEERC D번
사용 알고리즘
- Convex Hull
시간복잡도
- O(NlgN)
풀이
주어지는 점들로 일단 볼록껍질을 만들어줍시다.
이런식으로 볼록껍질이 만들어졌다고 합시다.
문제에서 요구하는 것은 볼록껍질의 둘레가 아닌, 볼록껍질에서 L만큼(초록색) 떨어진 노란색과 하늘색의 길이의 합입니다.
노란색의 길이의 합은 볼록껍질의 둘레와 동일합니다. 이제, 부채꼴 형태의 하늘색만 처리해주면 됩니다.
두 초록색 선 사이의 각을 θ라고 한다면, 검은색으로 그려져있는 두 벡터 A, B의 사잇각은 pi-θ가 됩니다.
두 벡터의 사잇각은 벡터의 내적과 acos함수를 이용해 쉽게 구할 수 있습니다.
반지름의 길이가 L이고, 중심각이 θ인 호의 길이는 L*θ라는 것을 이용해 정답을 구할 수 있습니다.
전체 코드
1 |
|