01708번 볼록 껍질

Problem link: https://www.acmicpc.net/problem/01708

Keywords: Convex Hull, Graham's Scan

이 문제는 convex hull을 찾는 문제이고, 관련한 알고리즘은 Graham’s scan에서 살펴본 바 있다.

Graham’s scan을 사용하면 별 탈 없이 풀리지만, 문제에서 조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.라는 추가 조건을 주기 때문에 조금 더 생각할 부분이 있다.

이 문제에서는 180도 미만의 polygon을 찾을 것이기 때문에, 외적의 값이 0이 아닌 양수가 나올 때 해당 점을 스택에 넣어주게 될 것이다.

이 부분에서 생각할 부분이 생기는데, 아래 그림이 보이는 예제를 살펴보자.

처음으로 고른 점이 그림에서 적색 점이었다고 하자.

만약, 점들을 오로지 각만을 기준으로 정렬한다면 위의 그림이 예시하는 순서의 정렬도 얼마든지 나올 수 있다(0 -> 1 -> 2에 주목).

이 상태에서 Graham’s scan을 진행하면 \(\overrightarrow{01} \times \overrightarrow{12} = 0\)이 나오기 때문에, 1번 정점이 스택에서 pop이 되어버린다.

1번 정점은 반드시 포함이 되어야 하는 정점인데도 말이다.

문제에서 특별한 조건이 없었다면, \(\overrightarrow{01} \times \overrightarrow{12} = 0\)이 나오는 경우도 반시계 방향으로 판단하고 스택에 넣어주면 그만인데 여기서는 그런 접근이 불가하다.

따라서, 이 문제에서는 각 점들을 각과 기준점으로부터의 거리를 기준으로하여 정렬한 뒤 문제를 풀어주면 된다.

아래는 솔루션이다.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

// Inputs.
class Vector2D;
int N;
vector<Vector2D> P;

// Solution.
constexpr double kEpsilon = 1e-9;

class Vector2D {
 public:
  Vector2D() = default;
  Vector2D(double x, double y) : x_(x), y_(y) {}

  double x() const { return x_; }
  double y() const { return y_; }

  Vector2D operator+(const Vector2D& rhs) const {
    return Vector2D(x_ + rhs.x_, y_ + rhs.y_);
  }
  Vector2D operator-(const Vector2D& rhs) const {
    return Vector2D(x_ - rhs.x_, y_ - rhs.y_);
  }
  bool operator<=(const Vector2D& rhs) const {
    if (x_ != rhs.x_) {
      return x_ <= rhs.x_;
    }
    return y_ <= rhs.y_;
  }
  double GetCcw(const Vector2D& v) const { return x_ * v.y_ - y_ * v.x_; }
  double GetAzimuth() const { return atan2(y_, x_); }
  double GetSquaredNorm() const { return x_ * x_ + y_ * y_; }

 private:
  double x_ = 0.0;
  double y_ = 0.0;
};

size_t Solve() {
  int lowest_point_idx = 0;
  for (int i = 1; i < N; ++i) {
    if (P[i] <= P[lowest_point_idx]) {
      lowest_point_idx = i;
    }
  }
  swap(P[0], P[lowest_point_idx]);
  sort(P.begin() + 1, P.end(),
       [p = P[0]](const Vector2D& lhs, const Vector2D& rhs) {
         const auto lhs_angle = (lhs - p).GetAzimuth();
         const auto rhs_angle = (rhs - p).GetAzimuth();
         if (abs(lhs_angle - rhs_angle) > kEpsilon) {
           return lhs_angle < rhs_angle;
         } else {
           return (lhs - p).GetSquaredNorm() < (rhs - p).GetSquaredNorm();
         }
       });

  vector<Vector2D> stack;
  stack.push_back(P[0]);
  stack.push_back(P[1]);
  for (int i = 2; i < N; ++i) {
    if (stack.size() < 2) {
      stack.push_back(P[i]);
    } else {
      const auto& curr = stack[stack.size() - 1];
      const auto& prev = stack[stack.size() - 2];
      const auto& p = P[i];
      if ((curr - prev).GetCcw(p - curr) > kEpsilon) {
        stack.push_back(p);
      } else {
        stack.pop_back();
        --i;
      }
    }
  }
  return stack.size();
}

int main(void) {
  // For faster IO.
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read inputs.
  cin >> N;
  for (int i = 0; i < N; ++i) {
    double x, y;
    cin >> x >> y;
    P.emplace_back(x, y);
  }

  // Solve.
  cout << Solve() << "\n";

  return 0;
}