개발일지

개념 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좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋..

개념 Counter Clock Wise 알고리즘의 줄임말이다. 세 점의 외적의 성질을 이용하는 알고리즘으로 보통 세점의 방향이 시계, 반시계, 직선인지 판별한다. 또한 외적의 성질을 이용하여 세 점이 이루는 삼각형의 넓이를 알 수 있다. 작동원리 세 점을 크로스 곱하여 그 값이 양수면 반 시계, 0이면 직선, 음수면 시계방향이다. 크로스 곱하여 2로 나누면 세 점이 이루는 삼각형의 크기이다. 시간복잡도 세 점을 외적할 때 -> 1 -> O(1) 문제 11758 CCW www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2,..