#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; } struct Vec2 { double x, y; Vec2(double x = 0, 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 double norm() const { return sqrt(x * x + y * y); } inline double norm_sq() const { return x * x + y * y; } inline Vec2 normalised() const { double l = norm(); return Vec2(x / l, y / l); } inline static double dot(const Vec2 &v1, const Vec2 &v2) { return v1.x * v2.x + v1.y * v2.y; } inline static double cross(const Vec2 &v1, const Vec2 &v2) { return v1.x * v2.y - v1.y * v2.x; } inline static double angle(const Vec2 &v1, const Vec2 &v2) { return abs(acos(dot(v1.normalised(), v2.normalised()))); } inline static bool is_ccw(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_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; } }; 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; Triangulation() {} inline void add_edge(int i, int j) { adj[i].push_back(j); adj[j].push_back(i); segments.emplace_back(i, j); } void init_by_x(int _n, Vec2 pt[]) { n = _n; for (int i = 2; i <= n; i++) for (int j = 1; j < i; j++) { bool is_crossing = false; Segment new_segment(pt[i], pt[j]); for (const auto &old_segment_idx : segments) { int x, y; tie(x, y) = old_segment_idx; if (Segment::intersect_strict(new_segment, Segment(pt[x], pt[y]))) { is_crossing = true; break; } } if (not is_crossing) add_edge(j, i); } } void init_by_length(int _n, Vec2 pt[]) { n = _n; vector<tuple<double, int, int>> all_segments; for (int i = 1; i <= n; i++) for (int j = 1; j < i; j++) all_segments.emplace_back((pt[i] - pt[j]).norm_sq(), j, i); sort(all_segments.begin(), all_segments.end()); for (const auto &segment : all_segments) { int i, j; tie(ignore, i, j) = segment; cerr << setprecision(10) << fixed; cerr << "considering segment " << i << " " << j << ", length = " << sqrt(get<0>(segment)) << endl; bool is_crossing = false; Segment new_segment(pt[i], pt[j]); for (const auto &old_segment_idx : segments) { int x, y; tie(x, y) = old_segment_idx; if (Segment::intersect_strict(new_segment, Segment(pt[x], pt[y]))) { is_crossing = true; break; } } if (not is_crossing) add_edge(i, j); } } }; struct Cross { vector<pair<double, double>> pt_angles_up; vector<pair<double, double>> pt_angles_down; bool crossed; Cross(int N, Vec2 pt[], int x, int y) { for (int p = 1; p <= N; p++) if (x != p and y != p) { Vec2 XP = pt[p] - pt[x]; Vec2 YP = pt[p] - pt[y]; Vec2 XY = pt[y] - pt[x]; Vec2 YX = pt[x] - pt[y]; double alpha = Vec2::angle(XP, XY); 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); } // crossed = false; // for (int a = 1; a <= N; a++) // if (x != a and y != a) // for (int b = a + 1; b <= N; b++) // if (x != b and y != b) // { // if (Segment::intersect_strict(Segment(pt[a], pt[b]), Segment(pt[x], pt[y]))) // crossed = true; // } } inline bool is_not_crossed() { for (const auto &angles_up : pt_angles_up) for (const auto &angles_down : pt_angles_down) { double alpha_up, beta_up, alpha_down, beta_down; tie(alpha_up, beta_up) = angles_up; tie(alpha_down, beta_down) = angles_down; if (alpha_up + alpha_down <= PI and beta_up + beta_down <= PI) return false; } return true; // return not crossed; } }; const int MAX = 1000 + 5; int N; Vec2 pt[MAX]; Triangulation<MAX> triangulation; 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_x); triangulation.init_by_x(N, pt); } void solve() { int ans = 0; for (const auto &e : triangulation.segments) { int x, y; tie(x, y) = e; ans += Cross(N, pt, x, y).is_not_crossed() ? 1 : 0; } cout << ans; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); input(); solve(); return 0; }