#include using namespace std; using ll = long long; using ld = long double; // vector OA = (x, y) template struct vec{ T x, y; vec (T xx=0, T yy=0) : x(xx), y(yy) {}; vec operator-() const { return vec(-x, -y); } vec& operator+=(const vec &w) { x += w.x; y += w.y; return *this; } vec& operator-=(const vec &w) { x -= w.x; y -= w.y; return *this; } vec operator+(const vec &w) const { vec res(*this); return res += w; } vec operator-(const vec &w) const { vec res(*this); return res-=w; } vec operator*=(T a){ x *= a; y *= a; return *this; } vec operator*(T a){ vec res(*this); return res*=a; } pair to_pair() {return {x, y};} }; //Inner product of vectors v and w template T dot(vec v, vec w){ return v.x * w.x + v.y * w.y; } //Outer product of vector v and w template T outer(vec v, vec w){ return v.x * w.y - w.x * v.y; } template vec normalize(vec &a){ T x=a.x, y=a.y, g; if (x == 0) return vec((T)0,y/abs(y)); else if (y == 0) return vec(x/abs(x), (T)0); g = abs(gcd(x, y)); return vec(x/g, y/g); } //size of triangle ABC template T heron(vec &a, vec &b, vec &c){ return abs(outer(b-a, c-a)) / 2; } //size of polygon A1A2...An template T area(vector> P){ int n=P.size(); T S=0; for (int i=0; i T distance(vec &a, vec &b){ return dot(a-b, a-b); } //Manhattan distance between point a and b template T manhattan(vec &a, vec &b){ return abs(a.x-b.x)+abs(a.y-b.y); } //Argument of complex template T arg(vec a){ complex c(a.x, a.y); T res = arg(c); if (res < 0) res += M_PI*2; return res; } //rotation around origin template vec rotate(vec &a, T theta){ complex c(a.x, a.y), p = polar((T)1, theta); c *= p; return vec(real(c), imag(c)); } //Convex Hull(Smallest Convex set containing all given vecs) //Grahum Scan (O(NlogN)) template vector> convex_hull(vector> P){ sort(P.begin(), P.end(), [](vec &p1, vec &p2) { if (p1.x != p2.x) return p1.x < p2.x; return p1.y < p2.y; }); int N=P.size(), k=0, t; vector> res(N*2); for (int i=0; i 1 && outer(res[k-1]-res[k-2], P[i]-res[k-1]) <= 0) k--; res[k] = P[i]; k++; } t = k; for (int i=N-2; i>=0; i--){ while(k > t && outer(res[k-1]-res[k-2], P[i]-res[k-1]) <= 0) k--; res[k] = P[i]; k++; } res.resize(k-1); return res; } //Sorting by argument(O(NlogN)) template void arg_sort(vector> &P){ int N=P.size(); vector> U, L; for (int i=0; i 0) U.push_back(P[i]); else if (P[i].y < 0) L.push_back(P[i]); else{ assert (P[i].x != 0); if (P[i].x > 0) U.push_back(P[i]); else L.push_back(P[i]); } } auto key=[](vec const &a, vec const &b)->bool{ return outer(a, b) > 0;}; sort(U.begin(), U.end(), key); sort(L.begin(), L.end(), key); P = U; for (auto &x : L) P.push_back(x); } //judge if segment AB intersects segment CD template bool intersect(vec &a, vec &b, vec &c, vec &d){ T s, t; s = outer(b-a, c-a); t = outer(b-a, d-a); if (s == 0 && t == 0){ if (max(a.x, b.x)max(c.x, d.x) || min(a.y, b.y)>max(c.y, d.y)) return 0; else return 1; } if ((s > 0 && t > 0) || (s < 0 && t < 0)) return 0; s = outer(d-c, a-c); t = outer(d-c, b-c); if ((s > 0 && t > 0) || (s < 0 && t < 0)) return 0; return 1; } //straight line template struct line{ //ax+by+c=0 T a, b, c; // Ax+By+C=0 line (T A=0, T B=0, T C=0) : a(A), b(B), c(C) {}; // line passing through p and q line (vec &p, vec &q) {a = (q.y-p.y); b = (p.x-q.x); c = -p.x*q.y + p.y*q.x;}; T slope() {return (b == 0 ? numeric_limits::infinity() : -a/b);} T intercept() {return (b == 0 ? numeric_limits::infinity() : -c/b);} }; //Intersection of straight lines p and q template vec intersection(line &p, line &q){ T coef = - (T)1/(p.a*q.b-q.a*p.b), x, y; x = (q.b*p.c-p.b*q.c) * coef; y = (-q.a*p.c+p.a*q.c) * coef; return vec(x, y); } //distance between line PQ and point R template T dist_line_point(vec &p, vec &q, vec &r){ // ax+by+c=0 T a = (q.y-p.y), b = (p.x-q.x), c = -p.x*q.y + p.y*q.x; return abs(a*r.x+b*r.y-c) / sqrt(a*a+b*b); }; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll N, ans=0; ll x, y, d; cin >> N; vector> p(N); for (int i=0; i> x >> y; p[i] = vec(x, y); } vector> v; for (int i=0; i st; for (int i=1; i