#include <bits/stdc++.h> using namespace std; const double PI = acos(-1); template <class T1, class T2> inline bool minimise(T1 &x, T2 y) { if (x > y) { x = y; return true; } return false; } template <class T1, class T2> inline bool maximise(T1 &x, T2 y) { if (x < y) { x = y; return true; } return false; } template <class T> inline constexpr int sgn(T x) { if (x > 0) return 1; if (x < 0) return -1; return 0; } template <int N> struct FenwickTree { int n, bit[N]; inline void init(int _n) { n = _n; } inline void add(int i, int v) { for (; i <= n; i += i & -i) bit[i] += v; } inline int get(int i) { int res = 0; for (; i > 0; i -= i & -i) res += bit[i]; return res; } }; struct Vec2 { long double x, y; Vec2(long double x = 0, long double y = 0) : x(x), y(y) {} inline Vec2 operator+(const Vec2 &oth) const { return Vec2(x + oth.x, y + oth.y); } inline Vec2 operator-(const Vec2 &oth) const { return Vec2(x - oth.x, y - oth.y); } inline long double arg() { return atan2(y, x); } inline long double norm() const { return sqrtl(x * x + y * y); } inline long double norm_sq() const { return x * x + y * y; } inline Vec2 normalised() const { long double l = norm(); return Vec2(x / l, y / l); } inline static long double arg(const Vec2 &v) { return atan2(v.y, v.x); } inline static long double dot(const Vec2 &v1, const Vec2 &v2) { return v1.x * v2.x + v1.y * v2.y; } inline static long double cross(const Vec2 &v1, const Vec2 &v2) { return v1.x * v2.y - v1.y * v2.x; } inline static long double angle(const Vec2 &v1, const Vec2 &v2) { long double dot_prod = dot(v1.normalised(), v2.normalised()); dot_prod = min(1.0L, max(-1.0L, dot_prod)); // cerr << "\t angle (" << v1.x << "," << v1.y << ") - (" << v2.x << "," << v2.y << ") " // << " --> acos = " << dot_prod // << " ==> " << acos(dot_prod) << endl; // return acos(dot(v1.normalised(), v2.normalised())); return acos(dot_prod); } inline static bool is_ccw_origin(const Vec2 &origin, const Vec2 &p1, const Vec2 &p2) { Vec2 r1 = p1 - origin; Vec2 r2 = p2 - origin; return cross(r1, r2) > 0.; } inline static bool is_ccw_turn(const Vec2 &p1, const Vec2 &p2, const Vec2 &p3) { Vec2 r1 = p2 - p1; Vec2 r2 = p3 - p2; return cross(r1, r2) > 0.; } inline static bool is_ray_order(const Vec2 &ray_1, const Vec2 &ray_mid, const Vec2 &ray_2, bool strict = false) { int _sgn = sgn(cross(ray_mid, ray_1)) * sgn(cross(ray_mid, ray_2)); if (strict) return _sgn < 0; return _sgn <= 0; } // inline tuple<const int &, const int &> coords() const // { // return tie(x, y); // } inline static bool compare_x(const Vec2 &v1, const Vec2 &v2) { if (v1.x != v2.x) return v1.x < v2.x; return v1.y < v2.y; } inline static bool compare_larger_x(const Vec2 &v1, const Vec2 &v2) { if (v1.x != v2.x) return v1.x > v2.x; return v1.y > v2.y; } inline static bool compare_y(const Vec2 &v1, const Vec2 &v2) { if (v1.y != v2.y) return v1.y < v2.y; return v1.x < v2.x; } }; struct Segment { Vec2 pt[2]; Segment(Vec2 A, Vec2 B) { pt[0] = A, pt[1] = B; } inline static bool intersect(Segment p, Segment q, bool strict = false) { Vec2 p1 = p.pt[0], p2 = p.pt[1]; Vec2 q1 = q.pt[0], q2 = q.pt[1]; return Vec2::is_ray_order(q1 - p1, p2 - p1, q2 - p1, strict) and Vec2::is_ray_order(p1 - q1, q2 - q1, p2 - q1, strict); } inline static bool intersect_strict(Segment p, Segment q) { return intersect(p, q, true); } }; template <int N> struct Triangulation { int n; vector<int> adj[N]; vector<pair<int, int>> segments; vector<int> hull; Triangulation() {} inline void add_edge(int i, int j) { adj[i].push_back(j); adj[j].push_back(i); segments.emplace_back(i, j); // cerr << "add " << i << " " << j << endl; } void init(int _n, Vec2 pt[]) { n = _n; add_edge(1, 2); add_edge(1, 3); add_edge(2, 3); // for (int i = 1; i <= n; i++) // cerr << "point " << i << ": " << pt[i].x << " " << pt[i].y << endl; if (not Vec2::is_ccw_turn(pt[1], pt[2], pt[3])) hull = {1, 2, 3}; else hull = {1, 3, 2}; for (int i = 4; i <= n; i++) { // cerr << "hull: "; // for (int e : hull) // cerr << e << " "; // cerr << endl; int p_min_arg = 0, p_max_arg = 0; long double min_arg = 2 * PI, max_arg = -2 * PI; for (int p = 0; p < hull.size(); p++) { long double arg = Vec2::arg(pt[hull[p]] - pt[i]); if (minimise(min_arg, arg)) p_min_arg = p; if (maximise(max_arg, arg)) p_max_arg = p; // cerr << "arg " << i << " -> " << hull[p] << ": " << arg << endl; } for (int p = p_min_arg;; p = (++p) % hull.size()) { add_edge(hull[p], i); if (p == p_max_arg) break; } vector<int> new_hull; for (int p = p_max_arg;; p = (++p) % hull.size()) { new_hull.push_back(hull[p]); if (p == p_min_arg) break; } new_hull.push_back(i); swap(hull, new_hull); } } }; struct Cross { int n; Vec2 *pt; vector<pair<long double, long double>> pt_angles_up; vector<pair<long double, long double>> pt_angles_down; vector<long double> min_betas_down; inline void init(int _n, Vec2 _pt[]) { n = _n; pt = _pt; } inline bool is_not_crossed(int x, int y) { pt_angles_up.clear(); pt_angles_down.clear(); min_betas_down.clear(); for (int p = 1; p <= n; p++) { if (x == p or y == p) continue; Vec2 XP = pt[p] - pt[x]; Vec2 YP = pt[p] - pt[y]; Vec2 XY = pt[y] - pt[x]; Vec2 YX = pt[x] - pt[y]; long double alpha = Vec2::angle(XP, XY); long double beta = Vec2::angle(YP, YX); if (Vec2::cross(XY, XP) > 0) pt_angles_up.emplace_back(alpha, beta); else pt_angles_down.emplace_back(alpha, beta); } sort(pt_angles_up.begin(), pt_angles_up.end()); sort(pt_angles_down.begin(), pt_angles_down.end()); for (const auto &e : pt_angles_down) min_betas_down.push_back(e.second); partial_sum( min_betas_down.begin(), min_betas_down.end(), min_betas_down.begin(), [&](long double x, long double y) -> long double { return min(x, y); }); auto it_up = pt_angles_up.begin(); auto it_down = pt_angles_down.rbegin(); auto it_min_beta_down = min_betas_down.rbegin(); while (it_up != pt_angles_up.end()) { while (it_down != pt_angles_down.rend() and it_up->first + it_down->first > PI) it_down++, it_min_beta_down++; if (it_min_beta_down != min_betas_down.rend() and *it_min_beta_down + it_up->second <= PI) return false; it_up++; } return true; } }; const int MAX = 1000 + 7; int N; Vec2 pt[MAX]; Triangulation<MAX> triangulation; Cross cross_counter; void input() { cin >> N; for (int i = 1; i <= N; i++) { int x, y; cin >> x >> y; pt[i] = Vec2(x, y); } sort(pt + 1, pt + N + 1, Vec2::compare_larger_x); triangulation.init(N, pt); cross_counter.init(N, pt); } void solve() { int ans = 0; for (const auto &e : triangulation.segments) { int x, y; tie(x, y) = e; if (cross_counter.is_not_crossed(x, y)) { // cerr << x << " " << y << " " << 1 << endl; ans += 1; } else { // cerr << x << " " << y << " " << 0 << endl; } } cout << ans; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); input(); solve(); return 0; }