https://www.acmicpc.net/problem/1708
동적계획법 DP에서 특정 형태의 점화식이 사용되었을 때, 시간복잡도를 획기적으로 줄여주는 방법Graham Scan 방식과 Jarvis March 방식이 있다.나는 Graham Scan 방식을 이용할 것.
Graham Scan Point를 잡는 동영상이다. 매우 친절하니 한번 보도록 하자.
시간복잡도는 O(NlogN)
절차를 설명해보자면1. y가 가장 작은 점을 구한다.2. 그 점을 기준으로 직선의 각을 정렬한다.3. 가장 작은점부터 조사하여 블록 껍질 확인 후 추가한다.
코드를 뜯어가며 살펴보자..
struct pos {
long long x,y;
};
x, y 좌표를 구조체로 선언해주었다. pair로 하려다가 그냥 구조체로 했다.. 짧고 좋은 듯
for (int i=1; i<t; i++){ //1부터
if(v[i].y < v[0].y || (v[i].y == v[0].y && v[i].x < v[0].x)){
long long temp = v[0].x;
v[0].x = v[i].x;
v[i].x = temp;
temp = v[0].y;
v[0].y = v[i].y;
v[i].y = temp;
}
}