알고리즘/기하
2021. 2. 25.
컨벡스 헐
2차원 평면위에 점들이 있습니다. 이 점들 중 일부를 골라 볼록 다각형을 만들었을 때, 나머지 점들이 모두 다각형 안에 포함된다면 이 다각형을 컨벡스 헐(Convex Hull, 볼록 껍질)이라고 합니다. 볼록 껍질을 구해 봅시다. www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 좌표 평면 위에 다음과 같이 점들이 있다고 가정해 봅시다. 이 중 y좌표가 가장 작은 점, 같다면 x좌표가 가장 작은 점을 하나 찾습니다. (기준은 바뀌어도 됩니다..
