Dev_Diary

https://www.acmicpc.net/problem/4225볼록 껍질 문제의 응용입니다.도형이 통과할 수 있는 구멍의 최솟값을 구하라는 것은 도형의 폭 중 가장 작은 값을 찾으라는 말과 같습니다.그렇다면 도형의 폭의 최솟값은 어떻게 구해야 할까요? 1. 볼록 껍질에 속해있는 점들 사이의 거리?결론부터 말하자면 아닙니다.붉은 선이 점들을 이은 선입니다.붉은 선도 폭들의 하나이긴 하지만 하늘색 선에 비하면 길이가 긴 것을 알 수 있습니다. 2. 변에서 점 사이의 거리그림에서 힌트가 나와있습니다.볼록 껍질에 속하는 변에서 볼록껍질에 속하는 점 까지의 거리들 중 최댓값이 해당 변에서 측정한 도형의 폭 이라고 할 수 있습니다.  즉 변에서 점 사이의 거리들의 최댓값 중 최솟값을 찾으면 폭의 최솟값을 찾을 수..

https://www.acmicpc.net/problem/10254지난번에 포스팅한 문제와 같은 알고리즘을 사용하지만 이번에는 단순 계산으로는 시간초과가 발생하므로 회전하는 캘리퍼스 알고리즘으로 문제를 풀었습니다. 회전하는 캘리퍼스는 특정한 도형에서 가장 먼 두 꼭지점을 찾는데 아주 유용한 알고리즘입니다.어떠한 점 A 에서 가장 먼 점 B 를 구할 때 점 A 를 지나는 직선 A' 를 정하면 그 직선과 평행하고 점 B 를 지나는 직선 B' 는 항상 존재합니다. 또한 직전의 점 B- 와 점 B 를 잇는 벡터 B'- 와 점 B 와 직후의 점 B+ 를 잇는 벡터 B'+ 는 각각 B' 와 이루는 외적값의 부호가 반대입니다.즉 (B-, B) : B'- / B' 와 B' / (B, B+) : B'+ 가 이루는 외적값..

https://www.acmicpc.net/problem/9240볼록껍질 + 회전하는 캘리퍼스 문제이지만우선 볼록껍질만 구하면 단순 계산으로 모든 볼록껍질에 속하는 점들 사이의 거리를 비교해도 풀 수 있습니다. 볼록껍질의 경우 C++" data-og-description="https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 " data-og-host="dev-diary-0717.tistory.com" data-og-source-url="https://dev-diary-0717.tistory.com/141..