// https://onlinejudge.u-aizu.ac.jp/beta/room.html#TUPC2021/problems/K #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } struct Pt { Int x, y; Pt() {} Pt(Int x, Int y) : x(x), y(y) {} Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); } Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); } Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); } Pt operator+() const { return Pt(+x, +y); } Pt operator-() const { return Pt(-x, -y); } Pt operator*(const Int &k) const { return Pt(x * k, y * k); } Pt operator/(const Int &k) const { return Pt(x / k, y / k); } friend Pt operator*(const Int &k, const Pt &a) { return Pt(k * a.x, k * a.y); } Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; } Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; } Pt &operator*=(const Pt &a) { return *this = *this * a; } Pt &operator*=(const Int &k) { x *= k; y *= k; return *this; } Int abs2() const { return x * x + y * y; } Int dot(const Pt &a) const { return x * a.x + y * a.y; } Int det(const Pt &a) const { return x * a.y - y * a.x; } friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; } }; constexpr Int EPS = 0; int sig(Int r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; } Int tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); } bool iSSStrict(const Pt &a, const Pt &b, const Pt &c, const Pt &d) { return (sig(tri(a, b, c)) * sig(tri(a, b, d)) < 0 && sig(tri(c, d, a)) * sig(tri(c, d, b)) < 0); } vector convexHull(vector ps) { const int n = ps.size(); sort(ps.begin(), ps.end(), [&](const Pt &a, const Pt &b) { return ((a.x != b.x) ? (a.x < b.x) : (a.y < b.y)); }); vector qs; for (int i = 0; i < n; qs.push_back(ps[i++])) for (; qs.size() > 1 && sig(tri(qs[qs.size() - 2], qs[qs.size() - 1], ps[i])) <= 0; qs.pop_back()) {} const size_t r = qs.size(); for (int i = (int)ps.size() - 2; i >= 0; qs.push_back(ps[i--])) for (; qs.size() > r && sig(tri(qs[qs.size() - 2], qs[qs.size() - 1], ps[i])) <= 0; qs.pop_back()) {} qs.pop_back(); return qs; } int N; // vector A; vector P; int main() { for (; ~scanf("%d", &N); ) { // A.resize(N); // for (int u = 0; u < N; ++u) { // scanf("%lld", &A[u]); // } P.resize(N); for (int u = 0; u < N; ++u) { scanf("%lld%lld", &P[u].x, &P[u].y); } // for (int u = 0; u < N; ++u) { // vector ps; // for (int v = 0; v < N; ++v) if (u != v) { // ps.push_back(A[v] * (P[v] - P[u])); // } #define ps P const auto qs = convexHull(ps); vector> es; for (const Pt &p : ps) { es.emplace_back(p, 1); } es.emplace_back(Pt(+1, 0), 0); es.emplace_back(Pt(0, +1), 0); es.emplace_back(Pt(-1, 0), 0); es.emplace_back(Pt(0, -1), 0); sort(es.begin(), es.end(), [&](const pair &a_, const pair &b_) { const Pt &a = a_.first; const Pt &b = b_.first; const int sa = (a.y > 0) ? 1 : (a.y < 0) ? 3 : (a.x > 0) ? 0 : 2; const int sb = (b.y > 0) ? 1 : (b.y < 0) ? 3 : (b.x > 0) ? 0 : 2; return ((sa != sb) ? (sa < sb) : (a.det(b) > 0)); }); const int esLen = es.size(); const int qsLen = qs.size(); // cerr<<"es = ";pv(es.begin(),es.end()); // cerr<<"qs = ";pv(qs.begin(),qs.end()); Int ans = 0; { int k = 0; for (int h = 0; h < 2; ++h) for (int j = 0; j < esLen; ++j) { for (; ; ) { int kk = k + 1; if (kk >= qsLen) kk -= qsLen; if (es[j].first.det(qs[kk] - qs[k]) > 0) { k = kk; } else { break; } } // cerr<<" "<