[BOJ/Platinum 2] 백준 10254 고속도로(C++)

문제 링크

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

10254번: 고속도로

 

 

문제

n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다.

고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 중 유클리드 거리가 가장 먼 두 도시를 찾으려 한다. 모든 도시는 한 평면 위에 있다.

위의 예제에서는 (12,0)의 도시와 (-6,3)의 도시가 가장 먼 유클리드 거리를 갖는다.

도시 n개의 좌표가 주어지면 모든 두 도시 쌍의 거리 중 가장 먼 두 도시를 찾아라.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 

각 테스트 케이스의 첫 줄엔 도시의 개수 n이 주어진다. (2 ≤ n ≤ 200,000) 그 후 n줄에 걸쳐 각 도시의 x좌표와 y좌표가 주어진다. (-10,000,000 ≤ x, y ≤ 10,000,000) x, y는 항상 정수이며, 어떤 두 도시가 같은 점 위에 있는 경우는 없다.

출력

테스트 케이스마다 가장 먼 두 점의 좌표를 출력한다.

만일 그 두 점의 좌표가 각각 (x1, y1), (x2, y2)이라면 x1 y1 x2 y2를 출력하면 된다.

가장 먼 거리를 갖는 두 점의 쌍이 여러 개라면 그 중 아무 것이나 출력해도 상관없다.

예제 입력 1

2
4
-100 -50
20 -50
-20 50
100 50
9
-1 -1
3 -3
6 -6
-3 -6
12 0
3 4
-6 3
0 9
6 9

예제 출력 1

-100 -50 100 50
-6 3 12 0

알고리즘 분류

• 그레이엄 스캔
• 회전하는 캘리퍼스

풀이

가장 먼 두 도시를 찾아야 하므로 가장자리에 있는 도시들을 먼저 거른다.

기준점을 정하고 그레이엄 스캔을 통해 가장자리에 있는 도시들만 찾는다.

도시의 개수가 최대 20만개까지 등장하기 때문에 이중반복문으로 비교한다면 시간 초과가 발생한다.

그러므로 회전하는 캘리퍼스를 활용한다.

제일 먼저 X좌표가 가장 작은 점과 큰 점을 기준으로 한다. 그리고 두 점 사이의 거리를 구한다.

다음으로 각각의 점의 다음 점과의 벡터를 구하고 두 벡터를 외적 계산한다. 계산한 값이 0보다 작으면 왼쪽 벡터의 끝 점을 갱신해준다. 0보다 크면 오른쪽 벡터의 끝 점을 갱신해준다. 그리고 새로 갱신한 두 점 사이의 거리를 구해서 기존의 최댓값과 비교해 최댓값을 갱신하고 두 점을 새로 갱신한다.

이 방법으로 모든 가장자리의 도시를 탐색하여 거리의 최댓값을 갖는 두 점을 구해준다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define INF 2e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct POINT {
    LL X, Y;
};

LL T, N, X, Y, minX, minY, First, Left, Right, maxD, X1, Y1, X2, Y2;
POINT Center;
vector<POINT> Point;
vector<POINT> CV;

void init() {
    minX = INF;
    minY = INF;
    First = 0;
    Left = 0;
    Right = 0;
    Center.X = 0;
    Center.Y = 0;
    Point.clear();
    CV.clear();
    maxD = 0;
}

LL distance(POINT A, POINT B) {
    return (A.X - B.X) * (A.X - B.X) + (A.Y - B.Y) * (A.Y - B.Y);
}

LL CCW(POINT A, POINT B, POINT C) {
    LL OP = ((A.X * B.Y) + (B.X * C.Y) + (C.X * A.Y));
    OP -= ((A.Y * B.X) + (B.Y * C.X) + (C.Y * A.X));
    return OP;
}

bool Comp(POINT A, POINT B) {
    LL NowCCW = CCW(Point[0], A, B);
    if (NowCCW > 0) {
        return true;
    }
    else if (NowCCW < 0) {
        return false;
    }
    if (A.X != B.X) {
        return (A.X < B.X);
    }
    return (A.Y < B.Y);
}

void graham_Scan() {
    for (int i = 0; i < Point.size(); i++) {
        if ((minX > Point[i].X) || ((minX == Point[i].X) && (minY > Point[i].Y))) {
            minX = Point[i].X;
            minY = Point[i].Y;
            First = i;
        }
    }
    swap(Point[0], Point[First]);
    sort(Point.begin() + 1, Point.end(), Comp);
    for (int i = 0; i < Point.size(); i++) {
        while ((CV.size() >= 2) && (CCW(Point[i], CV[CV.size() - 2], CV[CV.size() - 1]) <= 0)) {
            CV.pop_back();
        };
        CV.push_back(Point[i]);
    }
}

void rotating_Calipers() {
    for (int i = 0; i < CV.size(); i++) {
        if (CV[i].X < CV[Left].X) {
            Left = i;
        }
        else if (CV[i].X > CV[Right].X) {
            Right = i;
        }
    }
    maxD = distance(CV[Left], CV[Right]);
    X1 = CV[Left].X;
    Y1 = CV[Left].Y;
    X2 = CV[Right].X;
    Y2 = CV[Right].Y;
    for (int i = 0; i < CV.size(); i++) {
        POINT Prev, Next;
        Prev.X = CV[(Left + 1) % (int)CV.size()].X - CV[Left].X;
        Prev.Y = CV[(Left + 1) % (int)CV.size()].Y - CV[Left].Y;
        Next.X = CV[Right].X - CV[(Right + 1) % (int)CV.size()].X;
        Next.Y = CV[Right].Y - CV[(Right + 1) % (int)CV.size()].Y;
        if (CCW(Center, Prev, Next) > 0) {
            Left = (Left + 1) % (int)CV.size();
        }
        else {
            Right = (Right + 1) % (int)CV.size();
        }
        if (maxD < distance(CV[Left], CV[Right])) {
            maxD = distance(CV[Left], CV[Right]);
            X1 = CV[Left].X;
            Y1 = CV[Left].Y;
            X2 = CV[Right].X;
            Y2 = CV[Right].Y;
        }
    }
}

void settings() {
    graham_Scan();
    rotating_Calipers();
}

void find_Answer() {
    cout << X1 << " " << Y1 << " " << X2 << " " << Y2 << "\n";
}

void input() {
    cin >> T;
    while (T--) {
        init();
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> X >> Y;
            POINT Tmp;
            Tmp.X = X;
            Tmp.Y = Y;
            Point.push_back(Tmp);
        }
        settings();
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}