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

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

using ll = long long;
using i128 = __int128_t;

struct Point {
    ll x, y;
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

// ccw using (b-a) x (c-b)
static inline i128 ccw128(const Point& a, const Point& b, const Point& c) {
    ll dx1 = b.x - a.x, dy1 = b.y - a.y;
    ll dx2 = c.x - b.x, dy2 = c.y - b.y;
    return (i128)dx1 * (i128)dy2 - (i128)dx2 * (i128)dy1;
}
static inline i128 area2(const Point& a, const Point& b, const Point& c) {
    i128 v = ccw128(a, b, c);
    return v >= 0 ? v : -v;
}

struct Line {
    int i, j;      // point IDs (1..n) in the current labeling
    ll dx, dy;     // direction normalized so that dx >= 0
    Line(int a, int b, const vector<Point>& v) : i(a), j(b) {
        dx = v[i].x - v[j].x;
        dy = v[i].y - v[j].y;
        if (dx < 0) { dx = -dx; dy = -dy; }
    }
    bool operator<(const Line& t) const {
        return (i128)dy * (i128)t.dx < (i128)t.dy * (i128)dx;
    }
};

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

    int n;
    if (!(cin >> n)) return 0;
    vector<Point> v(n + 1);
    for (int i = 1; i <= n; ++i) cin >> v[i].x >> v[i].y;

    // Sort points by (x,y). Maintain idx[id] = current position of point id in v[1..n]
    sort(v.begin() + 1, v.begin() + n + 1);
    vector<int> idx(n + 1);
    for (int i = 1; i <= n; ++i) idx[i] = i;

    // Build all undirected lines (i, j) with i > j, normalized by angle (dx >= 0)
    vector<Line> lines; lines.reserve((size_t)n * (n - 1) / 2);
    for (int i = 1; i <= n; ++i) for (int j = 1; j < i; ++j) lines.emplace_back(i, j, v);
    sort(lines.begin(), lines.end());

    long long diagonalCredits = 0;         // sum over pairs L*R
    i128 minArea = -1;                     // minimal doubled area
    long long twiceMinAreaCount = 0;       // +2 per minimal quadrilateral overall

    for (const auto& e : lines) {
        int a = e.i, b = e.j;

        // Apply the adjacent swap corresponding to this line event
        swap(v[idx[a]], v[idx[b]]);
        swap(idx[a], idx[b]);

        int pa = idx[a], pb = idx[b];
        if (pa > pb) swap(pa, pb);

        // Count quadrilaterals where (a,b) is a diagonal: points strictly on each side
        diagonalCredits += 1LL * (pa - 1) * (n - pb);

        // Check 4 minimal-area candidates around the diagonal (pa,pb)
        for (int x = max(1, pa - 2); x <= pa - 1; ++x) {
            for (int y = pb + 1; y <= min(n, pb + 2); ++y) {
                i128 now = area2(v[x], v[pa], v[pb]) + area2(v[y], v[pa], v[pb]);
                if (minArea == -1 || now < minArea) { minArea = now; twiceMinAreaCount = 0; }
                if (now == minArea) {
                    ++twiceMinAreaCount; // base +1
                    i128 s1 = ccw128(v[x], v[y], v[pa]);
                    i128 s2 = ccw128(v[x], v[y], v[pb]);
                    if ((s1 > 0) == (s2 > 0)) ++twiceMinAreaCount; // non-convex adds one more
                }
            }
        }
    }

    cout << (diagonalCredits + twiceMinAreaCount) << '\n';
    return 0;
}