BOJ - 볼록 껍질(1708)

골드1 : 기하 문제이다.

생각

볼록 껍질, Convex Hull이라 한다. 이 알고리즘에서 유명한 것을 그라함 스캔 알고리즘인데, 해당 동영상을 봐보자.

이것과 같은 알고리즘을 구현하기 위해서는 다음과 같은 절차를 거쳐야 한다.

1. 가장 y가 작은 점을 구한다.
2. 그 점을 기준으로 직선의 각을 기준으로 정렬한다.
3. 각이 가장 작은 점부터 조사하면서 볼록 껍질인지 아닌지 확인하고 추가한다.

이 때, 각을 기준으로 정렬을 수행해야 하는데, 각은 double 형이라 이를 정렬하는데 좋지 않다. 일단 구하기도 어렵고 같은 선상에 있을 때 골치가 아프다..

그래서 이 때 각을 대변해 줄 수 있는 다른 지표로 외적의 부호를 사용한다. 이 부분이 달달한 부분인데, 외적의 값은 x, y축을 기저로 보았을 때, 시계 방향, 반시계 방향을 대변해 준다. 이 때, 특정 두 점과의 외적을 수행하면 서로의 상대적 위치를 알 수 있다.

이 연산을 점들을 각 순서로 정렬하는 비교 연산으로 사용하자.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
struct Point{
    ll x, y;
};
vector<Point> p;
int N;
 
ll ccw(Point p1, Point p2, Point p3){
    return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - (p2.x*p1.y + p3.x*p2.y + p1.x*p3.y);
}
 
bool compareMinelement(Point p1, Point p2){
    if (p1.y == p2.y) return p1.x < p2.x;
    else return p1.y < p2.y;
}
 
bool compareCCW(Point p1, Point p2){
    ll cp = ccw(p[0], p1, p2);
    if (cp == 0) return (p1.x + p1.y) < (p2.x + p2.y);
    return cp > 0;
}
 
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    p.resize(N);
 
    for (int i = 0; i < N; i++) {
        cin >> p[i].x >> p[i].y;
    }
 
    sort(p.begin(), p.end(), compareMinelement);
    sort(p.begin()+1, p.end(), compareCCW);
 
    vector<Point> v;
    v.push_back(p[0]);
    v.push_back(p[1]);
 
    // 이 for문은 세점 중 가장 바깥쪽 점을 의미
    for (int i = 2; i < N; i++) {
        // 볼록을 찾을 때까지 계속 진행
        while (v.size() >= 2) {
            // 두개를 본다.
            Point p2 = v.back();
            v.pop_back();
            Point p1 = v.back();
            // ccw이면 중간에 있는 점(p2)를 확인된 점으로 판단하고 스택에 넣는다.
            if (ccw(p1, p2, p[i]) > 0) {
                v.push_back(p2);
                break;
            }
            // ccw가 아니면 p2를 추가하지 말고 p2이전의 2점과 현재 p[i]와 ccw인지 비교한다. (처음으로 돌아간다)
        }
        // while문을 통과했다면 점이 추가가 된 것이므로 현재 탐색하는 가장 바깥쪽 점도 넣어준다.
        v.push_back(p[i]);
    }
    cout << v.size() <<  '\n';
}

보다 깔끔한 Convex Hull Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
struct Point {
   ll x, y;
   Point(ll a, ll b) :x(a), y(b) {};
   Point() {};
   bool operator<(const Point &rhs) const {
      if (x != rhs.x) return x < rhs.x;
      return y < rhs.y;
   }
};
vector<Point> point;
 
ll ccw(Point pt1, Point pt2, Point pt3) {
   ll ret = pt1.x*pt2.y + pt2.x*pt3.y + pt3.x*pt1.y;
   ret -= (pt2.x*pt1.y + pt3.x*pt2.y + pt1.x*pt3.y);
   return ret;
}
ll dist(Point pt1, Point pt2) {
   ll dx = pt2.x - pt1.x;
   ll dy = pt2.y - pt1.y;
   return dx * dx + dy * dy;
}
 
int main(){
    int N;
    cin >> N;
    point.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> point[i].x >> point[i].y;
    }
    vector<Point> hull;
    swap(point[0], *min_element(point.begin(), point.end()));
    sort(point.begin() + 1, point.end(), [](Point x, Point y) {
       ll cw = ccw(point[0], x, y);
       if (cw == 0) return dist(point[0], x) < dist(point[0], y);
       return cw > 0;
    });
 
    for (auto i : point) {
        // hull의 뒤에서 2번째 값, 1번째 값, 그리고 point의 3번째 값을 비교하여
        // 반시계가 아니면 hull의 맨 뒤의 점을 뺀다.
        // 반시계이면 해당 점을 포함한 상태로 다음점을 비교한다.
       while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), i) <= 0) {
          hull.pop_back();
       }
       hull.push_back(i);
    }
    cout << hull.size() << endl;
}

Reference

• 백준(1708번) - 볼록 껍질