좌표 시계/반시계방향 정렬

convex hull을 다루는 문제에서 

좌표를 줄 때 시작부터 cw/ccw 방향으로 좌표를 주는 경우가 있다면

랜덤하게 좌표를 주는 경우 원하는 조건에 맞게 정렬하는 방법을 정리해보자

 

* 볼록껍질의 선분을 다루기 위해서 그 선분의 점이 되는 좌표들을 미리 정렬해야함

 

반시계 방향으로 정렬한다고 가정하고

 

기준점(보통 기준점으로 x,y의 끝값에 있는 좌표를 사용, 가장 바깥쪽에 있는 좌표면 충분)을 먼저 잡고

그 기준점을 기준으로 다른 모든 점들에 대한 각도(tan)를 구함

 

// arr[0]은 가장 바깥쪽(현재 x,y값이 가장 작은 좌표)
for (int i = 1; i < N; i++) {
    arr[i].p = arr[i].x - arr[0].x;
    arr[i].q = arr[i].y - arr[0].y;
}

 

구한 각도를 기준으로 정렬(이때 반시계방향으로 좌표가 정렬됨)

 

bool cmp(point& a, point& b) {
    if (1LL * a.p * b.q != 1LL * a.q * b.p) return 1LL * a.q * b.p < 1LL * a.p * b.q;
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

 

point& a 에서 tan값은 a.q / a.p 가 되는데 위와같이 정렬하는 이유는

/ => 나눗셈을 이용하게 되면 값이 0이 되는 부분(x의 차가 없거나,y의 차가 없거나)이

분모에 올 경우 정확한 답을 찾을 수 없기 때문

tan을 위와 다르게도 정렬할 수 있다. 어쨋든 각도를 이용해서 정렬만 하면 된다

 

hull 의 내부점이 될지 선분의 기준점이 될지는 ccw으로 판단한다(당장 반시계방향의 좌표를 구하므로)

 

스택과 ccw을 이용해서 convex hull을 찾는다

 

첫번째 인자는 기준점, 두번쨰 인자는 반시계방향의 첫번째 좌표, 세번째 인자는 반시계방향의 두번째 좌표

 

3번째 인자에 대한 ccw가 >0 이 되면 왼쪽에 위치하는 점이므로 볼록껍질의 좌표가 될 수 있는 부분,

그 이외는 좌표가 될 수 없는 부분이 된다

 

ccw 가 >0 이면 두번째인자를 스택에 푸쉬(그래야 다음 확인때 첫번째로 사용가능함), 세번째 인자 역시 스택에 푸쉬

 

단, 비교해야할 선분(1,2번째인자로 만든 선분)이 필요하므로 최소한 스택의 값은 2이상 유지되야한다

 

stack<int> s;
 
int next = 2;
s.push(0);
s.push(1);
while (next < N) {
    while (s.size() >= 2) {
        int first, second;
        second = s.top();
        s.pop();
        first = s.top();
            if (ccw(arr[first], arr[second], arr[next]) > 0) {
            s.push(second);
            break;
        }
    }
    s.push(next++);
}

 

이렇게 마지막 좌표까지 탐색하면 현재 스택에 남아있는 좌표가 반시계방향에 대한 좌표가 된다