기하알고리즘] 회전하는 캘리퍼스

캘리퍼스란?

캘리퍼스는 작은 물건의 지름,너비 등을 측정할 때 쓰는 도구로 두개의 평형한 변 사이의 길이를 측정하는 도구이다.

 

회전하는 캘리퍼스(Rotating Calipers) 알고리즘이란?

회전하는 캘리퍼스 알고리즘은 실제 볼록 다각형의 지름을 재는데 사용된다.

다각형을 따라 두 직선을 한바퀴 돌리면서 두 직선에 닿는 꼭지점들 간의 거리를 구하는 알고리즘이다.

백준 10254번 고속도로 문제를 기준으로 살펴 보자

https://www.acmicpc.net/problem/10254

10254번: 고속도로

Convex Hull 알고리즘으로 볼록 다각형 테두리를 찾아낸 후 각 꼭지점에서 가장 먼 거리를 측정하는 문제이다.

위와 같이 한변을 기준으로 회전 하면서 가장 먼 거리를 찾아 주면 된다.

기준점이 되는 한변을 선택 한다면(i와 i_next) 위와 같이 다른 선분을(j와 j_next)를 진행 하면서 위의 j와 j_next 부분에서는 멈추면 된다는 것을 알 수 있다.

i에서 i_next 와 j에서 j_next의 ccw 가 반시계 방향이라면 거리가 늘어 나지만 시계방향으로 바뀐다면 그 거리가 짧아 지는 것을 확인 할 수 있다.

따라서 각 i 점에서 위와 같이 ccw 를 구하여 시계방향의 위치에서 최장거리의 후보군으로 선택하는 알고리즘이다.

따라서 위의 문제는 다음과 같이 해결 할수 있다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>


#define INF 987654321987654321L

using namespace std;


struct Point {
    long long x, y;
    long long p, q;

    bool operator < (const struct Point &r) const{
        if (q * r.p !=  p*r.q)
            return q * r.p < p*r.q;
        //기울기가 같을때는 좌표값으로 정렬하자.
        if (y != r.y)
            return y < r.y;

        return x < r.x;
    }
};


/*
두개의 선분 이 다음과 같다고 하면
line 1 : (x1,y1) (x2,y2)
line 2 : (x3,y3) (x4,y4)
교차하지 않는 경우는 다음과 같다.
-dot3과 dot4가 모두 line1의 왼쪽에 있는 경우
-dot3과 dot4가 모두 line1의 오른쪽에 있는 경우
-dot1과 dot2가 모두 line2의 왼쪽에 있는 경우
-dot1과 dot2가 모두 line2의 오른쪽에 있는 경우

(x1,y1) (x2,y2) 의 기울기를 구하는 방정식 y증가량 / x증가량
기울기 a = (y2-y1) / (x2-x1)
(x3,y3) 이 오른쪽에 있는지 왼쪽에 있는지 구분하기 위해서는
(x1,y1) (x3,y3) 의 기울기를 구해서 기울기가 작은지 큰지를 구분하면 된다.
(y2-y1) / (x2-x1) - (y3-y1) / (x3-x1) > 0 이면 (x3,y3) 이 오른쪽에 있는 것이다.
이때 line 의 기울기가 음수일때는 왼쪽 오른쪽의 위치가 반대이다.
그리고 분모가 0 인경우 문제가 발생한다.
따라서 분모를 없애자...
(y2-y1)(x3-x1) - (y3-y1)(x2-x1) > 0 이면 오른쪽 <0 이면 왼쪽 ==0 이면 같다.
이렇게 하면 음수인 경우도 해결이 됨. 음수를 곱하면 부등호도 반대가 됨으로
*/

long long ccw(const Point &A, const Point &B, const Point &C) {
    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;
}

long long ptoplen(const Point &A,const Point &B){
    return (B.x-A.x)*(B.x-A.x) + (B.y-A.y)*(B.y-A.y);
}

Point p[200010];

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    int t;
    cin >> t;

    while(t--){
        long long miny=INF;
        long long minx=INF;
        long long minindex=-1;
        long long maxlen = 0;
        int n;
        cin >> n;

        for (int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            p[i].x=x;
            p[i].y=y;
            if(miny > y)
            {
                miny = y;
                minx = x;
                minindex=i;
            }
            else if(miny==y)
            {
                if(minx>x)
                {
                    miny = y;
                    minx = x;
                    minindex=i;
                }
            }
        }
        swap(p[0],p[minindex]); //y가 가장 작은 값을 0번지에 넣자.
        //sort(p, p + n, comp1);
        // 기준점으로부터 상대 위치 계산
        for (int i = 1; i < n; i++) {
            p[i].p = p[i].x - p[0].x;
            p[i].q = p[i].y - p[0].y;
        }

        // 반시계 방향으로 정렬(기준점 제외)
        sort(p + 1, p + n);

        stack<int> s;

        // 스택에 first, second를 넣어준다.
        s.push(0);
        s.push(1);

        int next = 2;

        while (next < n) {
            while (s.size() >= 2) {
                int first, second;
                second = s.top();
                s.pop();
                first = s.top();

                // first, second, next가 좌회전 ( > 0 )이라면 second push
                // 우회전( < 0 )이라면 위의 while문 계속 반복
                if (ccw(p[first], p[second], p[next]) > 0) {
                    s.push(second);
                    break;
                }
            }

            // next push
            s.push(next++);
        }
        /* 여기 까지는 Convex Hull 로 볼록 다각형을 찾아냄 */

        //볼록 다각형의 정점만 모으자.
        vector<Point> convexHull;
        Point ans1,ans2;
        while(!s.empty()){
            convexHull.push_back(p[s.top()]);
            s.pop();
        }

        int j=1;
        for(int i=0;i<convexHull.size();i++){
            int i_next = (i+1) % convexHull.size();
            while(1){
                int j_next = (j+1)%convexHull.size();
                Point temp = {0,0,0,0};
                Point point_i,point_j;
                point_i.x = convexHull[i_next].x - convexHull[i].x;
                point_i.y = convexHull[i_next].y - convexHull[i].y;

                point_j.x = convexHull[j_next].x - convexHull[j].x;
                point_j.y = convexHull[j_next].y - convexHull[j].y;

                if(ccw(temp,point_i,point_j)<0) j=j_next;
                else break;
            }
            long long len = ptoplen(convexHull[i],convexHull[j]);
            if(len > maxlen){
                maxlen = len;
                ans1 = convexHull[i];
                ans2 = convexHull[j];
            }
        }
        cout << ans1.x << " " << ans1.y << " " << ans2.x << " " << ans2.y << "\n";

    }

    return 0;
}