contest3.F.cpp

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

using namespace std;

static bool geoerror;

// #define USE_FLOAT
// #define USE_RELATIVE_ERROR

#ifdef USE_FLOAT
#define EPS 1e-9
#define nabs fabs
typedef double num;
#else
#define EPS 0
#define nabs(x) ((x) < 0 ? -(x) : (x))
typedef long long num;
#endif

bool num_lt(num X, num Y) {
#ifdef USE_RELATIVE_ERROR
  return X + max(num(1), nabs(Y)) * EPS < Y;
#else
  return X + EPS < Y;
#endif
}

bool num_lteq(num X, num Y) {
#ifdef USE_RELATIVE_ERROR
  return X <= Y + max(num(1), nabs(Y)) * EPS;
#else
  return X <= Y + EPS;
#endif
}

bool num_eq(num X, num Y) {
#ifdef USE_FLOAT
  return num_lteq(X, Y) && num_lteq(Y, X);
#else
  return X == Y;
#endif
}

typedef complex<num> point;
typedef vector<point> poly;

struct line {
  line(point norm, num C) : norm(norm), C(C) {}
  point norm;
  num C;
};

num cp(point A, point B, point C = point(0, 0)) {
  A -= C; B -= C;
  return A.real() * B.imag() - B.real() * A.imag();
}

/* Returns true if C counter-clockwise AB.  In other words as you walk from A to
 * B, C would be on your left.  */
bool ccw(point A, point B, point C) {
  return num_lt(0, cp(A, B, C));
}

bool ccweq(point A, point B, point C) {
  return num_lteq(0, cp(A, B, C));
}

num dot(point A, point B, point C = point(0, 0)) {
  A -= C; B -= C;
  return A.real() * B.real() + A.imag() * B.imag();
}

/* O(N log N) convex hull implementation. */
bool pointCmp(point A, point B) {
  return make_pair(A.real(), A.imag()) < make_pair(B.real(), B.imag());
}

point pivot;

bool angleCmp(point A, point B) {
  num c = cp(pivot, A, B);
  return num_eq(c, 0) && dot(A, A, pivot) < dot(B, B, pivot) || num_lt(0, c);
}

void unwind(poly& P, point A) {
  int sz = P.size();
  while(sz > 1 && ccweq(A, P[sz - 1], P[sz - 2])) --sz;
  P.resize(sz);
}

poly hull(poly P) {
  if (P.size() <= 2) return P;

  swap(P[0], *min_element(P.begin(), P.end(), pointCmp));
  pivot = P[0];
  sort(P.begin() + 1, P.end(), angleCmp);

  poly ret(1, pivot);
  for(int i = 1; i < P.size(); i++) {
    unwind(ret, P[i]);
    ret.push_back(P[i]);
  }
  unwind(ret, pivot);
  return ret;
}

/* Check if A is in the convex polygon P (in ccw order). */
bool in_convex(poly& P, point A, bool on) {
  if(ccw(P[0], A, P[1]) || ccw(P[0], P.back(), A)) return false;
  int lo = 1;
  int hi = P.size() - 2;
  while(lo < hi) {
    int md = (lo + hi + 1) / 2;
    if(ccw(P[0], P[md], A)) {
      lo = md;
    } else {
      hi = md - 1;
    }
  }
  return (on || lo != 1 ? ccweq : ccw)(P[0], P[lo], A) &&
         (on ? ccweq : ccw)(P[lo], P[lo + 1], A) &&
         (on || lo + 2 != P.size() ? ccweq : ccw)(P[lo + 1], P[0], A);
}

int main() {
  int N;
  num px, py;
  cin >> N >> px >> py;

  poly A;
  for(int i = 0; i < N; i++) {
    num x, y;
    cin >> x >> y;
    A.push_back(point(x, y));
  }

  for(int result = 0; ; result++) {
    poly H = hull(A);
    if (H.size() < 3 || !in_convex(H, point(px, py), false)) {
      cout << result << '\n';
      break;
    }

    poly B;
    for(int i = 0; i < A.size(); i++) {
      if(in_convex(H, A[i], false)) {
        B.push_back(A[i]);
      }
    }
    A.swap(B);
  }
  return 0;
}