Dev_Diary

https://www.acmicpc.net/problem/2254 2254번: 감옥 건설첫째 줄에 N(1 ≤ N ≤ 1,000), Px, Py (-100,000 ≤ Px, Py ≤ 100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다.www.acmicpc.net볼록 껍질 ( convex hull ) 알고리즘과 임의의 점이 다각형 안에 존재하는지 찾는 알고리즘을 함께 사용하면 풀 수 있습니다. 볼록 껍질 알고리즘은 아래 링크를 C++" data-og-description="https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 ..

https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 볼록 껍질, 즉 Convex Hull 문제입니다. 이 문제를 푸는 방법 중 보편적으로 알려져 있는 알고리즘은 그라함 스캔, 그라함 알고리즘으로 알려져 있습니다. 해당 알고리즘으로 문제를 풀어보겠습니다. 그라함 스캔을 사용하기 위해서는 CCW 알고리즘을 알아야 하는데, 외적을 이용하는 알고리즘으로 세 개의 점의 상태를 알 수 있습니다. 즉 세 개의 점이 하나의 직선 위에 있는지 ..