BOJ 2254: 감옥 건설

작성일

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

  • 3월동안 210문제 풀기 (8/210)
  • Convex Hull 만들고, 점이 내부에 있는것을 확인하는 문제
  • 점이 내부에 있으려면 Hull위의 인접한 두점과 그 점과의 CCW가 모두 양수이거나 모두 음수여야한다.
  • 당연한거지만 위 판단법은 Hull이 아니면 안됨.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;

typedef long long VType;
struct Vector {
  VType x, y;

  Vector() {}
  Vector(VType x, VType y): x(x), y(y) {}
  Vector(const Vector& other): x(other.x), y(other.y) {}
  Vector& operator+=(const Vector& other) {
    x += other.x;
    y += other.y;
    return (*this);
  }
  Vector operator+(const Vector &other) const {
    return Vector(*this) += other;
  }
  Vector& operator-=(const Vector& other) {
    x -= other.x;
    y -= other.y;
    return (*this);
  }
  Vector operator-(const Vector &other) const {
    return Vector(*this) -= other;
  }
  VType cross(const Vector& v2) const {
    return x*v2.y - v2.x*y;
  }
  int ccw(const Vector &v2) const {
    VType vccw = cross(v2);
    if(vccw > 0) return 1;
    if(vccw == 0) return 0;
    else return -1;
  }
};

vector<int> grahamScan(vector<Vector> &poly) {
  auto cmp = [](Vector& a, Vector& b) {
    return a.y < b.y || (a.y == b.y && a.x < b.x);
  };
  sort(poly.begin(), poly.end(), cmp);

  Vector origin = poly[0];
  for(Vector& v: poly) v -= origin;

  auto cmpCcw = [](Vector& a, Vector& b) {
    VType vccw = a.ccw(b);
    if(vccw != 0) return vccw > 0;
    return a.y < b.y || (a.y == b.y && a.x < b.x);
  };
  sort(poly.begin()+1, poly.end(), cmpCcw);

  vector<int> hull = {0,1};
  for(int i = 2; i < poly.size(); i++) {
    while(hull.size() >= 2) {
      int last = hull.back();
      hull.pop_back();
      Vector v1 = poly[i] - poly[last];
      Vector v2 = poly[hull.back()] - poly[last];
      if(v1.ccw(v2) <= 0) continue;
      hull.push_back(last);
      break;
    }
    hull.push_back(i);
  }
  for(Vector& v: poly) v += origin;
  return hull;
}

int main() {
  ios::sync_with_stdio(false);
  int N, Px, Py, x, y;
  cin >> N >> Px >> Py;
  vector<Vector> poly(N);
  for(int i = 0; i < N; i++)
    cin >> poly[i].x >> poly[i].y;
  Vector jail = {Px,Py};

  int ans = 0, DEL = 1e9;
  while(poly.size()) {
    auto hull = grahamScan(poly);
    bool success = true;;
    Vector v1 = poly[hull.back()] - jail;
    Vector v2 = poly[hull[0]] - jail;
    int first = v1.ccw(v2);
    for(int i = 1; i < hull.size(); i++) {
      Vector v1 = poly[hull[i-1]] - jail;
      Vector v2 = poly[hull[i]] - jail;
      int vccw = v1.ccw(v2);
      if(first*vccw <= 0) {
        success = false;
        break;
      }
    }
    for(int i: hull) poly[i].x = DEL;
    vector<Vector> newPoly;
    for(Vector& v: poly)
      if(v.x != DEL) newPoly.push_back(v);
    poly = newPoly;
    if(success) ans++;
    else break;
  }
  cout << ans;
}