99. Andrew's Algorithm

앤드류 알고리즘(Andrew's Algorithm)은 점 $n$개의 볼록 껍질을 $\Theta(n\text{ lg }n)$ 시간에 찾는 또다른 알고리즘으로, 앞에서 소개한 그레이엄의 스캔보다 구현이 간단한 편이다. 모노톤 체인(Monotone Chain)이라는 이름으로도 알려져 있다. 이 알고리즘은 점들을 정렬하는 기준을 각도 대신 좌표로 하며, 위쪽 껍질과 아래쪽 껍질을 따로 구하게 된다. 구체적인 작동 방법은 다음과 같다.

 

1. 점들을 $x$좌표가 증가하는 순서대로, $x$좌표가 같다면 $y$좌표가 증가하는 순서대로 정렬한다.
2. 점을 앞쪽부터 차례로 확인하면서 그레이엄의 스캔과 같은 방식으로 볼록 껍질을 찾는다. 마지막 점까지 확인하면 볼록 껍질의 윗부분이 완성된다.
3. 점을 뒤쪽부터 차례로 확인하면서 다시 볼록 껍질을 찾는다. 첫 번째 점까지 확인하면 볼록 껍질의 아랫부분이 완성된다.
4. 윗부분과 아랫부분을 합쳐서 볼록 껍질 전체를 완성한다.

앞에서 나온 그림을 다시 들고 와서 앤드류 알고리즘으로 볼록 껍질을 구하면 이렇게 된다.

첫 번째 점은 마찬가지로 점 $1$이고, 두 번째 점은 점 $6$이다. 두 점을 차례로 $S$에 추가한다.

점 $3$을 $S$에 추가한다.

점 $3$을 $S$에서 제거하고 점 $4$를 $S$에 추가한다.

점 $9$를 $S$에 추가한다.

점 $9$와 점 $4$를 $S$에서 제거하고 점 $8$을 $S$에 추가한다.

점 $7$을 $S$에 추가한다.

점 $5$를 $S$에 추가한다.

점 $5$, 점 $7$, 점 $8$을 $S$에서 제거하고 점 $2$를 $S$에 추가한다.

이렇게 하면 위쪽 볼록 껍질이 완성된다. 이제 아래쪽 볼록 껍질을 찾는데, 뒤에서 첫 번째 점인 점 $2$가 $S$에 있으므로 뒤에서 두 번째 점인 점 $5$를 $S$에 추가한다.

점 $7$을 $S$에 추가한다.

점 $7$을 $S$에서 제거하고 점 $8$을 $S$에 추가한다.

점 $8$을 $S$에서 제거하고 점 $9$를 $S$에 추가한다.

첨 $4$를 $S$에 추가한다.

점 $4$와 점 $9$를 $S$에서 제거하고 점 $3$을 $S$에 추가한다.

점 $6$을 $S$에 추가한다.

점 $6$을 $S$에서 제거하고 점 $1$을 $S$에 추가한다.

아래쪽 볼록껍질이 완성되었다.

 

이 방법은 위쪽과 아래쪽 볼록 껍질을 따로 만들기 때문에 점들을 두 번씩 확인하게 되지만 구현이 간단한 편이므로 유용하게 사용할 수 있다. 구현은 다음과 같다.

#import<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Point{LL i, x, y;} p[100005];
int a[100005];
int C(Point a, Point b){return a.x < b.x || a.x == b.x && a.y < b.y;}
LL ccw(LL x1, LL y1, LL x2, LL y2, LL x3, LL y3)
{
    LL t = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
    if(t > 0)return 1;
    else if(t < 0)return -1;
    else return 0;
}
int main()
{
    int k = 0, n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        p[i].i = i + 1;
        cin >> p[i].x >> p[i].y;
    }
    sort(p, p + n, C);
    for(int i = 0; i < n;)
    {
        if(k < 2 || ccw(p[a[k - 2]].x, p[a[k - 2]].y, p[a[k - 1]].x, p[a[k - 1]].y, p[i].x, p[i].y) < 0)a[k++] = i++;
        else k--;
    }
    a[k++] = n - 2;
    for(int i = n - 1; i >= 0;)
    {
        if(a[k - 1] == n - 1 || ccw(p[a[k - 2]].x, p[a[k - 2]].y, p[a[k - 1]].x, p[a[k - 1]].y, p[i].x, p[i].y) < 0)a[k++] = i--;
        else k--;
    }
    k--;
    for(int i = 0; i < k; i++)a[i] = p[a[i]].i;
}

 

$\text{a}$ 배열 대신 vector를 이용해서 구현할 수도 있다.

#import<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Point{LL i, x, y;} p[100005];
vector<int>v;
int C(Point a, Point b){return a.x < b.x || a.x == b.x && a.y < b.y;}
LL ccw(LL x1, LL y1, LL x2, LL y2, LL x3, LL y3)
{
    LL t = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
    if(t > 0)return 1;
    else if(t < 0)return -1;
    else return 0;
}
int main()
{
    int k = 0, n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        p[i].i = i + 1;
        cin >> p[i].x >> p[i].y;
    }
    sort(p, p + n, C);
    for(int i = 0; i < n;)
    {
        if(k < 2 || ccw(p[v[k - 2]].x, p[v[k - 2]].y, p[v[k - 1]].x, p[v[k - 1]].y, p[i].x, p[i].y) < 0)
        {
            v.push_back(i++);
            k++;
        }
        else
        {
            v.pop_back();
            k--;
        }
    }
    v.push_back(n - 2);
    k++;
    for(int i = n - 1; i >= 0; )
    {
        if(v[k - 1] == n - 1 || ccw(p[v[k - 2]].x, p[v[k - 2]].y, p[v[k - 1]].x, p[v[k - 1]].y, p[i].x, p[i].y) < 0)
        {
            v.push_back(i--);
            k++;
        }
        else
        {
            v.pop_back();
            k--;
        }
    }
    k--;
    for(int i = 0; i < k; i++)v[i] = p[v[i]].i;
}

 

[연습문제]

 

BOJ 1708. 볼록 껍질 (Platinum V)

볼록 껍질에 포함되는 점의 개수를 구하면 된다.

 

BOJ 3878. 점 분리 (Platinum II)

검은색 점들로 볼록 껍질을 만들고, 흰색 점들로 볼록 껍질을 만들었을 때 두 볼록 껍질을 직선으로 분리할 수 있어야 한다. 따라서 두 볼록 껍질이 만나지 않아야 하고, 한 볼록 껍질이 다른 볼록 껍질의 안에 있는 경우도 고려해야 한다. 전자는 각각의 변끼리 교차 여부를 전부 확인하면 알 수 있고, 후자는 모든 점들로 볼록 껍질을 만들었을 때 볼록 껍질에 포함된 점들 중 검은색 점과 흰색 점이 모두 있는지 확인하면 알 수 있다. 구현이 어렵다는 의견이 많은 것 같은데 개인적으로는 이 방법으로 접근하면 예외도 없고 구현도 꽤 간단하다고 생각한다.

 

CF 1299C. Water Balance (2100)

각각의 원소를 누적합으로 바꾼 뒤 좌표가 $(i, a_i)$인 점으로 생각하고 아래쪽 볼록껍질을 구하면 $x$좌표가 $i$인 지점에서의 볼록 껍질의 기울기가 $i$번째로 출력하는 값이 된다.

 

→ solved.ac tag: point_in_convex_polygon