컨벡스 헐

2차원 평면위에 점들이 있습니다.

이 점들 중 일부를 골라 볼록 다각형을 만들었을 때, 나머지 점들이 모두 다각형 안에 포함된다면 이 다각형을 컨벡스 헐(Convex Hull, 볼록 껍질)이라고 합니다.

 

볼록 껍질을 구해 봅시다.

 

www.acmicpc.net/problem/1708

1708번: 볼록 껍질

좌표 평면 위에 다음과 같이 점들이 있다고 가정해 봅시다.

 

이 중 y좌표가 가장 작은 점, 같다면 x좌표가 가장 작은 점을 하나 찾습니다. (기준은 바뀌어도 됩니다)

그 점을 기준으로, 나머지 점들을 각도 순으로 정렬해 봅시다.

각도순 정렬은 삼각함수등을 이용해도 되지만, CCW를 이용하면 편리합니다.

 

각도가 같을경우 기준점과의 거리를 기준으로 정렬합니다

이 점들을 차례대로 방문하며 스택에 넣으면서, 볼록 껍질을 만들어 봅시다.

반시계 방향으로 볼록 껍질을 만들어 간다고 한다면, 스택에서 연속된 세점을 어떻게 고르더라도 CCW가 0보다 커야 합니다. (좌회전)

 

 

만약 새로운 점을 스택에 추가했을 때 그 점을 포함한 연속된 세점의 CCW가 0보다 작다면 (우회전), 그렇지 않을 때까지 스택에서 마지막 점을 제거하면 됩니다.

 

이 작업을 마지막 점까지 반복하면 컨벡스 헐을 구할 수 있게 됩니다.

 

시간복잡도는 점 정렬에 \(O(n\log n)\), 후작업에 \(O(n)\)이므로, 총 \(O(n\log n)\)입니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
pll p2v(pll a, pll b) // 두 점 A,B가 주어지면 벡터 AB를 반환
{
    return { b.first - a.first, b.second - a.second };
}
 
ll ccw(pll v1, pll v2) // 벡터 v1, v2의 CCW
{
    ll res = v1.first * v2.second - v1.second * v2.first;
 
    if (res > 0) return 1;
    else if (res < 0) return -1;
    else return 0;
}
 
ll dist2(pll a, pll b) // 점 A,B사이의 거리의 제곱
{
    ll dx = a.first - b.first;
    ll dy = a.second - b.second;
    return dx * dx + dy * dy;
}
 
int n;
pii point[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> point[i].first >> point[i].second;
        if (point[i] < point[0]) swap(point[0], point[i]);
    }
 
    sort(point + 1, point + n, [](pii a, pii b) {
        // 각도순 정렬
        pll v1 = p2v(point[0], a);
        pll v2 = p2v(point[0], b);
        ll res = ccw(v1, v2);
 
        if (res) return res > 0; 
        return dist2(point[0], a) < dist2(point[0], b);
        // 세 점이 일직선에 있다면 거리 순으로 정렬
    });
 
    vector <pll> CH;
 
    for (int i = 0; i < n; i++)
    {
        while (CH.size() > 1)
        {
            pll p1 = CH[CH.size() - 2];
            pll p2 = CH[CH.size() - 1];
            pll p3 = point[i];
 
            pll v1 = p2v(p1, p2);
            pll v2 = p2v(p2, p3);
 
            ll res = ccw(v1, v2);
            if (res > 0) break;
 
            CH.pop_back();
        }
 
        CH.push_back(point[i]);
    }
 
    cout << CH.size();
}

---

컨벡스 헐을 이용하는 문제 중 하나는 가장 먼 두 점을 구하는 것입니다.

 

나이브하게 생각하면 컨벡스 헐을 구한 다음, 컨벡스 헐에 속하는 점의 모든 쌍을 검사하여 \(O(n^2)\)에 구할 수 있습니다.

더 빠른 방법인 회전하는 캘리퍼스 알고리즘에 대해 알아봅시다.

 

컨벡스 헐에 속한 점 중 x좌표가 가장 작은 점과 가장 큰 점을 찾아 기준으로 잡아봅시다. (역시 기준은 바뀌어도 됩니다)

이 상태에서 캘리퍼스(초록색 선)을 다각형을 따라 반시계 방향으로 돌려봅시다.

현재 기준인 두 점의 (컨벡스 헐 기준) 다음 점 두 개중에서, 캘리퍼스와 더 먼저 닿는 점을 새로운 기준 점으로 잡는 것을 반복하면 됩니다.

 

두 점 중 어떤 점이 먼저 닿는지는 역시 나이브하게 계산해도 되지만, 역시 CCW를 이용하면 편리합니다.

 

맨 왼쪽 그림에서, \(\overrightarrow{AB} \times \overrightarrow{DC}\)가 0보다 크면 \(\theta _1\)이 더 작고, 0보다 작으면 \(\theta _2\)가 더 작음을 알 수 있습니다.

 

지금까지 기준이었던 점 쌍의 거리(빨간 선)의 최대값이 가장 먼 두 점이 됩니다.

캘리퍼스의 회전은 많아도 컨벡스 헐의 크기만큼 하게 되므로, 시간복잡도는 \(O(n)\)입니다.

 

www.acmicpc.net/problem/10254

10254번: 고속도로

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
pll p2v(pll a, pll b) // 두 점 A,B가 주어지면 벡터 AB를 반환
{
    return { b.first - a.first, b.second - a.second };
}
 
ll ccw(pll v1, pll v2) // 벡터 v1, v2의 CCW
{
    ll res = v1.first * v2.second - v1.second * v2.first;
 
    if (res > 0) return 1;
    else if (res < 0) return -1;
    else return 0;
}
 
ll dist2(pll a, pll b) // 점 A,B사이의 거리의 제곱
{
    ll dx = a.first - b.first;
    ll dy = a.second - b.second;
    return dx * dx + dy * dy;
}
 
int n;
pii point[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> point[i].first >> point[i].second;
            if (point[i] < point[0]) swap(point[0], point[i]);
        }
 
        sort(point + 1, point + n, [](pii a, pii b) {
            // 각도순 정렬
            pll v1 = p2v(point[0], a);
            pll v2 = p2v(point[0], b);
            ll res = ccw(v1, v2);
 
            if (res) return res > 0;
            return dist2(point[0], a) < dist2(point[0], b);
            // 세 점이 일직선에 있다면 거리 순으로 정렬
            });
 
        vector <pll> CH;
 
        for (int i = 0; i < n; i++)
        {
            while (CH.size() > 1)
            {
                pll p1 = CH[CH.size() - 2];
                pll p2 = CH[CH.size() - 1];
                pll p3 = point[i];
 
                pll v1 = p2v(p1, p2);
                pll v2 = p2v(p2, p3);
 
                ll res = ccw(v1, v2);
                if (res > 0) break;
 
                CH.pop_back();
            }
 
            CH.push_back(point[i]);
        }
 
        int i1 = min_element(CH.begin(), CH.end()) - CH.begin();
        int i2 = max_element(CH.begin(), CH.end()) - CH.begin();
        // 기준점 2개를 잡는다
 
        ll mxDist = 0;
        int ans1 = -1, ans2 = -1;
 
        for (int i = 0; i < CH.size(); i++)
        {
            pll p1 = CH[i1], p1_nxt = CH[(i1 + 1) % CH.size()];
            pll p2 = CH[i2], p2_nxt = CH[(i2 + 1) % CH.size()];
 
            ll curDist = dist2(p1, p2);
            if (curDist > mxDist)
            {
                mxDist = curDist;
                ans1 = i1, ans2 = i2;
            }
 
            pll v1 = p2v(p1, p1_nxt);
            pll v2 = p2v(p2_nxt, p2);
 
            if (ccw(v1, v2) > 0) i1 = (i1 + 1) % CH.size();
            else i2 = (i2 + 1) % CH.size();
            // 더 각도가 작은 쪽으로 캘리퍼스 회전
        }
 
        cout << CH[ans1].first << ' ' << CH[ans1].second << ' '
            << CH[ans2].first << ' ' << CH[ans2].second << '\n';
    }
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217