codeforces Hello 2020 - E. New Year and Castle Construction

(待补)

Kiwon's favorite video game is now holding a new year event to motivate the users! The game is about building and defending a castle, which led Kiwon to think about the following puzzle.

In a 2-dimension plane, you have a set consisting of distinct points. In the set , no three distinct points lie on a single line. For a point , we can protect this point by building a castle. A castle is a simple quadrilateral (polygon with vertices) that strictly encloses the point p (i.e. the point p is strictly inside a quadrilateral).

Kiwon is interested in the number of subsets of that can be used to build a castle protecting . Note that, if a single subset can be connected in more than one way to enclose a point, it is counted only once.

Let be the number of 4-point subsets that can enclose the point p. Please compute the sum of for all points .

Input

The first line contains a single integer .

In the next lines, two integers and denoting the position of points are given.

It is guaranteed that all points are distinct, and there are no three collinear points.

Output

Print the sum of for all points .

Examples

input

5
-1 0
1 0
-10 -1
10 -1
0 3

output

2

input

8
0 1
1 2
2 2
1 3
0 -1
-1 -2
-2 -2
-1 -3

output

40

input

10
588634631 265299215
-257682751 342279997
527377039 82412729
145077145 702473706
276067232 912883502
822614418 -514698233
280281434 -41461635
65985059 -827653144
188538640 592896147
-857422304 -529223472

output

213

凸包。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long double
const int maxn = 3005;
ll x[maxn], y[maxn];
int main(){
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> x[i] >> y[i];
    }
    long long res = (long long)n * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 24;
    ll pi = acos(-1.0L);
    for (int i = 0; i < n; i++){
        vector<ll> v;
        for (int j = 0; j < n; j++){
            if(i == j)
                continue;
            v.push_back(atan2(y[j]-y[i], x[j]-x[i]));
        }
        sort(v.begin(), v.end());
        int m = n - 1, index = 0;
        for (int j = 0; j < m; j++){
            while(index<j+m){
                ll ang = v[index % m] - v[j];
                if(ang<0)
                    ang += pi * 2;
                if(ang<pi)
                    index++;
                else
                    break;
            }
            long long cnt = index - j - 1;
            res -= 1ll * cnt * (cnt - 1) * (cnt - 2) / 6;
        }
    }
    cout << res << endl;
    return 0;
}