볼록 껍질을 이용한 최적화 / Convex Hull Trick
CHT란?
동적계획법 DP에서 특정 형태의 점화식이 사용되었을 때, 시간복잡도를 획기적으로 줄여주는 방법Graham Scan 방식과 Jarvis March 방식이 있다.나는 Graham Scan 방식을 이용할 것.
Graham Scan
Graham Scan Point를 잡는 동영상이다. 매우 친절하니 한번 보도록 하자.
https://youtu.be/Ps1idzOx6LA
시간복잡도는 O(NlogN)
절차를 설명해보자면1. y가 가장 작은 점을 구한다.2. 그 점을 기준으로 직선의 각을 정렬한다.3. 가장 작은점부터 조사하여 블록 껍질 확인 후 추가한다.
코드를 뜯어가며 살펴보자..
구조체 선언부
struct pos {
long long x,y;
};
C++
복사
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;
}
}
C++
복사
1.
y좌표가 가장 적고 2.x좌표가 가장 작은 점이 먼저 나오도록 정렬한다.
반시계방향 정렬
sort(v.begin()+1, v.end(), compare);
C++
복사
0번째 원소를 시작점으로 n-1개의 점들을 각도가 작은 순서대로 다시 정렬한다.(내 코드상으로는 t-1개의 점)
long long ccw(pos a, pos b, pos c) { //CCW 알고리즘
return a.x * b.y + b.x * c.y + c.x * a.y - (b.x * a.y + c.x * b.y + a.x * c.y);
}
bool compare(pos a, pos b){ //반시계 정렬
long long cc = ccw(v[0], a, b);
if (cc) //각도가 작은 순
return cc>0;
else if (a.y != b.y) //y가 작은 순
return a.y < b.y;
else //x가 작은 순
return a.x < b.x;
}
Plain Text
복사
cww함수를 이용한 compare 함수이다.cww 알고리즘은 의한 것인데, 세 점 a, b, c가 있을 때 벡터 ab와 벡터 ac를 외적하여 양수가 나오면 세 점 a, b, c는 반시계 방향으로 위치함을 알 수 있다네요.역시나 1. y좌표가 가장 적고 2.x좌표가 가장 작은 점이 먼저 나오도록 정렬했다.
볼록 껍질 검사
s.push(v[0]);
s.push(v[1]);
for(int i=2; i<t; i++){
while (s.size() >= 2){
pos top2 = s.top();
s.pop();
pos top1 = s.top();
if (ccw(top1, top2, v[i]) > 0){
s.push(top2); //다시 push
break;
}
}
s.push(v[i]);
}
C++
복사
이제 정렬된 점이 있을때 2점을 스택에 넣어주고 검사를 시작한다.그러니까 스택의 상위 2점과 새로 잡은 점과 계속 ccw검사를 하며 확인하는 것.음수가 나오면 잘못된 선택이니 break한다.
for문이 끝나면 모든 점들에 대한 검사가 끝나고 스택에 블록 껍질 점들이 들어가 있다. 이 점들이 최종적으로 선택된 볼록 다각형의 꼭짓점들이다.
전체 코드
#include <iostream>#include <algorithm>#include <stack>#include <vector>
using namespace std;
struct pos {
long long x,y;
};
vector <pos> v;
stack <pos> s;
long long ccw(pos a, pos b, pos c) { //CCW 알고리즘
return a.x * b.y + b.x * c.y + c.x * a.y - (b.x * a.y + c.x * b.y + a.x * c.y);
}
bool compare(pos a, pos b){ //반시계 정렬
long long cc = ccw(v[0], a, b);
if (cc) //각도가 작은 순
return cc>0;
else if (a.y != b.y) //y가 작은 순
return a.y < b.y;
else //x가 작은 순
return a.x < b.x;
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin>>t;
v.resize(t);
for (int i=0; i<t; i++){
cin>>v[i].x>>v[i].y;
}
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;
}
}
sort(v.begin()+1, v.end(), compare);
s.push(v[0]);
s.push(v[1]);
for(int i=2; i<t; i++){
while (s.size() >= 2){
pos top2 = s.top();
s.pop();
pos top1 = s.top();
if (ccw(top1, top2, v[i]) > 0){
s.push(top2); //다시 push
break;
}
}
s.push(v[i]);
}
cout<<s.size();
return 0;
}
C++
복사
