BOJ 4181 Convex Hull

https://www.acmicpc.net/problem/4181

4181번: Convex Hull

 

말 그대로 컨벡스 헐을 구하는 문제입니다. 컨벡스 헐을 구할 수 있으면 그냥 구할 수 있습니다. 컨벡스 헐을 구할줄 몰라도 문제에서 어떤 점이 볼록 껍질에 포함되는지 알려주기 때문에 각도정렬을 슥삭슥삭 하면 구할 수 있습니다.

 

편의를 위해 반시계 방향의 시작점(x값이 가장 작은 점, 같다면 y값이 가장 작은 점)을 기준으로 기울기를 구해줍니다. 이렇게 하면 다른 모든 점들은 시작점의 오른쪽에 위치하기 때문에 180도의 범위만 각도정렬을 하면 됩니다. 이렇게 구한 기울기를 분수 형태로 관리하여 점들을 정렬해줍니다. 정렬할 때, 기울기가 같은 점이 여럿 있을 수 있으므로 (한 직선 위에 세 개 이상의 점이 있을 수 있으므로) 기울기가 같다면 x값을 기준으로 정렬해줍니다.

 

이렇게 하면 쉽게 답을 구할 수 있...지는 않습니다. 삼각형을 하나 생각해봅시다. 이 삼각형의 꼭짓점에 점이 찍혀있고 각 변의 중점에 점이 찍혀있는 경우 반시계 방향으로 돌았을 때의 마지막 변이 반대로 출력되게 됩니다. 따라서 마지막 점과 기울기가 같은 점들을 역순으로 출력해주면 됩니다.

 

기하 문제는 잘 풀지 않는데, 왜 안 푸는지 알 수 있었던 문제였습니다. 예외처리를 연습할 수 있는 교육적인 문제라고는 생각합니다. 근데 어려워요.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define int long long
#define FF first
#define SS second
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()

using namespace std;

struct point {
  int x, y, p, q;

  point() : x(0), y(0) {}
  point(int x, int y, int p, int q) : x(x), y(y), p(p), q(q) {}

  bool operator< (const point& rhs) const {
    if (p * rhs.q == rhs.p * q) {
      if (x == rhs.x) return y < rhs.y;
      else return x < rhs.x;
    }
    else return (p * rhs.q) > (rhs.p * q);
  }
};

int T, n;
vector<point> vec;

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n;

    vector<pii> tmp;
    
    for (int i = 0; i < n; i++) {
      int x, y;
      char c;
      cin >> x >> y >> c;
      if (c == 'Y') tmp.push_back({ x, y });
    }

    sort(all(tmp));
    int mnx = tmp[0].FF;
    int mny = tmp[0].SS;

    for (int i = 1; i < tmp.size(); i++) {
      auto [x, y] = tmp[i];
      int p = x - mnx;
      int q = y - mny;
      vec.push_back(point(x, y, p, q));
    }

    sort(all(vec));

    int last = vec.size() - 1;
    while (last && vec[vec.size() - 1].p * vec[last].q == vec[last].p * vec[vec.size() - 1].q) last--;

    cout << tmp.size() << endl;
    cout << mnx << ends << mny << endl;
    for (int i = 0; i <= last; i++) cout << vec[i].x << ends << vec[i].y << endl;
    for (int i = vec.size() - 1; i > last; i--) cout << vec[i].x << ends << vec[i].y << endl;
  }

  return 0;
}