[Baekjoon - 2049] 가장 먼 두 점

난이도: Platinum III

 

태그

• Convex Hull

 

풀이

1. 가장 먼 두 점의 후보가 될 수 있는 점은?

우선,입력받은 점들을 토대로 볼록 껍질을 만들어 봅시다.

볼록 껍질을 만드는 이유는, 볼록 다각형에서 가장 먼 두 점은 경계에 있는 두 점이기 때문입니다.

// 그렇지 않다면, 경계를 만날 때까지 더 늘릴 수 있겠죠.

 

다만 이게 가장 먼 두 점이 볼록 껍질에 포함된 점뿐임을 의미하진 않을수도 있습니다.

// 가장 먼 두 점이 꼭짓점이 아니라 변에 위치한 점이었다면? 그 점을 실제로는 다시 만들어낼 수 없으니 잘 생각해봐야겠죠.

즉, 이 부분에 대해서는 추가적으로 생각을 해봐야겠죠.

 

다행히도, 볼록 다각형에서 가장 먼 두 점은 항상 두 꼭짓점이 됩니다.

// 두 점을 잡아보고, 한 점을 꼭짓점으로 밀어봅시다.

// 멀어진다면, 그 쪽 방향으로 끝까지 밀어주면 됩니다.

// 가까워진다면, 반대쪽 방향으로 끝까지 밀어주면 됩니다.

// 다른 방식을 원한다면, 교차하지 않는 두 선분의 가장 먼 두 점은 선분의 꼭짓점끼리만 비교하면 된다는 걸 생각해보면 됩니다.

 

2. 근데 이거 Rotating Calipers 없이 되나요?

입력되는 점이 \( N \)개이므로, Convex Hull을 만들더라도

Rotating Calipers 없이 그냥 브루트 포스를 돌리면 \( O(N^2) \)이 나와야 할 것처럼 보입니다.

 

하지만, 실제로는 좌표 범위가 \( X \) 이하의 정수일 때 Convex Hull의 꼭짓점은 최대 \( O(\sqrt[3]{X^2}) \)개밖에 되지 않는다는 점을 사용하면, 브루트 포스를 돌려도 \( O(\sqrt[3]{X^4}) \)가 될 테니 문제 없이 AC를 받을 수 있습니다.

 

3. 코드

pl2 arr[100020];
vector<pl2> v;
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
    for (int i = 1; i <= n; i++){
        if (arr[1] > arr[i]){ swap(arr[1], arr[i]); }
    }
    pl2 p = arr[1]; sort(arr+2, arr+n+1, [p](pl2 p1, pl2 p2){
        int res = ccw(p, p1, p2);
        if (res != 0){ return res > 0; }
        return dis(p, p1) < dis(p, p2);
    });
    for (int i = 1; i <= n; i++){
        while (v.size() >= 2){
            int vl = v.size();
            if (ccw(v[vl-2], v[vl-1], arr[i]) <= 0){ v.pop_back(); }
            else{ break; }
        }
        v.push_back(arr[i]);
    }
    ll ans = 0;
    for (pl2 p1 : v){
        for (pl2 p2 : v){ ans = max(ans, dis(p1, p2)); }
    }
    cout << ans;
}