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
106
107
108
109
110

// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

using ld = long double;
const ld EPS = 1e-12L;

struct Pt {
  ld x, y;
  Pt() {}
  Pt(ld _x, ld _y): x(_x), y(_y) {}
  Pt operator+(const Pt& o) const { return Pt(x + o.x, y + o.y); }
  Pt operator-(const Pt& o) const { return Pt(x - o.x, y - o.y); }
  Pt operator*(ld k) const { return Pt(x * k, y * k); }
};

ld cross(const Pt& a, const Pt& b) { return a.x * b.y - a.y * b.x; }
ld dot(const Pt& a, const Pt& b) { return a.x * b.x + a.y * b.y; }

struct Line {
  Pt p;      // point on line
  Pt v;      // direction vector
  ld ang;    // angle for sorting
  Line() {}
  Line(Pt _p, Pt _v): p(_p), v(_v) { ang = atan2l(v.y, v.x); }
};

Pt intersect(const Line& a, const Line& b) {
  ld t = cross(b.v, b.p - a.p) / cross(b.v, a.v);
  return a.p + a.v * t;
}

bool inside_strict(const Line& l, const Pt& q) { return cross(l.v, q - l.p) > EPS; }

vector<Line> normalize_lines(vector<Line>& ls) {
  sort(ls.begin(), ls.end(), [](const Line& a, const Line& b) {
    if (fabsl(a.ang - b.ang) > 1e-15L) return a.ang < b.ang;
    return cross(a.v, b.p - a.p) > 0;
  });
  vector<Line> res;
  for (const auto& L : ls) {
    if (res.empty() || fabsl(L.ang - res.back().ang) > 1e-15L) res.push_back(L);
    else if (cross(res.back().v, L.p - res.back().p) > 0) res.back() = L;
  }
  return res;
}

bool halfplane_intersection_has_area(vector<Line> ls) {
  ls = normalize_lines(ls);
  deque<Line> dq;
  deque<Pt> ip;

  auto add = [&](const Line& L) {
    while (!ip.empty() && !inside_strict(L, ip.back())) { dq.pop_back(); ip.pop_back(); }
    while (!ip.empty() && !inside_strict(L, ip.front())) { dq.pop_front(); ip.pop_front(); }
    if (!dq.empty() && fabsl(cross(dq.back().v, L.v)) < 1e-18L) {
      if (inside_strict(L, dq.back().p)) { dq.pop_back(); if (!ip.empty()) ip.pop_back(); }
      else return;
    }
    if (!dq.empty()) ip.push_back(intersect(dq.back(), L));
    dq.push_back(L);
  };

  for (const auto& L : ls) add(L);

  while (!ip.empty() && !inside_strict(dq.front(), ip.back())) { dq.pop_back(); ip.pop_back(); }
  while (!ip.empty() && !inside_strict(dq.back(), ip.front())) { dq.pop_front(); ip.pop_front(); }

  if (dq.size() < 3) return false;
  vector<Pt> poly;
  for (size_t i = 0; i + 1 < dq.size(); ++i) poly.push_back(intersect(dq[i], dq[i + 1]));
  poly.push_back(intersect(dq.back(), dq.front()));

  ld area2 = 0;
  for (size_t i = 0; i < poly.size(); ++i) {
    size_t j = (i + 1) % poly.size();
    area2 += cross(poly[i], poly[j]);
  }
  return fabsl(area2) > 1e-10L;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; if (!(cin >> n)) return 0;
  vector<Pt> a(n);
  for (int i = 0; i < n; ++i) { long long x, y; cin >> x >> y; a[i] = Pt((ld)x, (ld)y); }

  auto feasible = [&](int k)->bool {
    vector<Line> ls; ls.reserve(n);
    for (int i = 0; i < n; ++i) {
      int j = (i + k + 1) % n;
      Pt p = a[i], q = a[j];
      Pt t = a[(j + 1) % n];
      if (cross(q - p, t - p) <= 0) swap(p, q);
      ls.emplace_back(p, q - p);
    }
    return halfplane_intersection_has_area(ls);
  };

  int lo = 0, hi = max(0, n - 3), best = 0;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (feasible(mid)) { best = mid; lo = mid + 1; }
    else hi = mid - 1;
  }
  cout << (best + 1) << '\n';
  return 0;
}