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 s = ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x n , y n ) s={(x1,y1),(x2,y2),…,(xn,yn)} s=(x1,y1),(x2,y2),…,(xn,yn) consisting of n n n distinct points. In the set s s s, no three distinct points lie on a single line. For a point p ∈ s p∈s p∈s, we can protect this point by building a castle. A castle is a simple quadrilateral (polygon with 4 4 4 vertices) that strictly encloses the point p (i.e. the point p is strictly inside a quadrilateral).

Kiwon is interested in the number of 4 − p o i n t 4-point 4−point subsets of s s s that can be used to build a castle protecting p p p. Note that, if a single subset can be connected in more than one way to enclose a point, it is counted only once.

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

Input

The first line contains a single integer n n n ( 5 ≤ n ≤ 2500 ) (5≤n≤2500) (5≤n≤2500).

In the next n n n lines, two integers x i xi xi and y i yi yi ( − 109 ≤ x i , y i ≤ 109 ) (−109≤xi,yi≤109) (−109≤xi,yi≤109) 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 $f§ $for all points p ∈ s p∈s p∈s.

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;
}