개발일지

개념 Convex Hull이란 2차원 평면 위에 점들이 있을 때 최소한의 정점으로 다른 정점들을 감싸는 알고리즘이다. 대표적인 알고리즘으로 Graham's Scan(그라함 스캔)이 있다. 작동원리 1. 정점을 반 시계 or 시계 방향으로 정렬한다. 2. Graham's Scan 알고리즘을 이용한다. 시간복잡도 정점을 정렬할 때 -> nlogn, Graham's Scan할 때 -> n -> O(nlogn) 문제 1708 블록 껍질 www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋..