볼록껍질 선분 처리하기

기하 문제중 볼록껍질(convex hull) 을 다룰 때 좌표가 주어지면 

이를 선분으로 처리하는 방법을 정리해두자

 

보통 문제에서는 볼록껍질의 좌표를 시계방향/시계반대방향으로 주어진다.

 

볼록껍질에서 좌표가 주어지면 이를 선분처리해서 사용할 줄 알아야한다.

 

한 선분은 두 점으로 이루어져있으니 인접한 좌표를 기준으로 처리해야한다.

 

시계반대방향을 기준으로 정리해본다

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
using namespace std;
 
struct point {
    int x, y;
};
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    // 입력은 볼록껍질의 좌표를 시계 반대방향으로 주어진다고 가정
    // 볼록껍질을 윗껍질의 선분집합, 아랫껍질의 선분집합으로 나눈다.
    vector<pair<point, point> > upper, lower;
 
    // 입력받을 좌표의 갯수 n
    int n; cin >> n;
 
    // 볼록껍질의 좌표를 모아둘 벡터
    vector<point> v;
 
    // 좌표는 int형으로 받는다고 가정하고 x n개 y n개를 받는다
    for (int i = 0; i < n; i++) {
        point a;
        cin >> a.x >> a.y;
        v.push_back(a);
    }
 
    // 시계 반대방향은 인접한 좌표의 x를 기준으로 보았을 때
    // x가 증가하는 부분은 아랫껍질에 해당하고
    // x가 증가하는 부분은 윗껍질에 해당한다
 
    // 윗껍질, 아랫껍질 선분집합으로 나누기
    for (int i = 0; i < v.size(); i++) {
        if (v[i].x < v[(i + 1) % n].x) {
            lower.push_back({ v[i], v[(i + 1) % n] });
        }
        else if (v[i].x > v[(i + 1) % n].x) {
            upper.push_back({ v[i], v[(i + 1) % n] });
        }
    }
 
    // 윗껍질 선분과 아랫껍질 선분을 모두 출력해보면
    for (int i = 0; i < lower.size(); i++) {
        cout << "아랫껍질 선분 (" << lower[i].first.x << "," << lower[i].first.y << ") (" << lower[i].second.x << "," << lower[i].second.y << ")\n";
    }
    for (int i = 0; i < upper.size(); i++) {
        cout << "윗껍질 선분 (" << upper[i].first.x << "," << upper[i].first.y << ") (" << upper[i].second.x << "," << upper[i].second.y << ")\n";
    }
 
    return 0;
}

 

제대로 코드되었는지 확인해보았다.