CodeForces - 1025F：Disjoint Triangles （几何）

A point belongs to a triangle if it lies inside the triangle or on one of its sides. Two triangles are disjoint if there is no point on the plane that belongs to both triangles.

You are given nn points on the plane. No two points coincide and no three points are collinear.

Find the number of different ways to choose two disjoint triangles with vertices in the given points. Two ways which differ only in order of triangles or in order of vertices inside triangles are considered equal.

Input

The first line of the input contains an integer nn (6≤n≤20006≤n≤2000) – the number of points.

Each of the next nn lines contains two integers xixi and yiyi (|xi|,|yi|≤109|xi|,|yi|≤109) – the coordinates of a point.

No two points coincide and no three points are collinear.

Output

Print one integer – the number of ways to choose two disjoint triangles.

Examples

Input

Output

Input

7
0 -1000000000
-5 -5
5 -5
-5 0
5 0
-2 2
2 2

Output

题意：现在有N个点，满足没有三点共线，问有对少对三角形，满足没有公共部分。

思路：如果两个三角形A，B不相交，则有两种方式满足：A选择一个点a，B选择一个点b，三角形AB被直线ab隔开。那么我们枚举直线，然后直线两侧的点数分别是x，y，则其贡献是C(x,2)*C(y,2)*2，*2是因为有a可以和x部分组合，也可以和y部分组合，但最后要/2，因为没对三角形有两种直线满足。

具体的，我们用到了atan2(y1-y2,x1-x2)，在一二象限为正，三四象限为负。

#include<bits/stdc++.h>

#define ll long long

#define pii pair<int,int>

#define pdd pair<double,double>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define F first

#define S second

using namespace std;

const double pi=acos(-1.0);

const int maxn=;

pdd a[maxn]; double w[maxn];

int main()

{

    int N; ll ans=;

    scanf("%d",&N);

    rep(i,,N) scanf("%lf%lf",&a[i].F,&a[i].S);

    rep(i,,N){

        int tot=;

        rep(j,,N) if(j!=i) w[++tot]=atan2(a[j].S-a[i].S,a[j].F-a[i].F); //纵坐标在前，横在后

        sort(w+,w++tot);

        for(int j=,k=;j<=tot&&w[j]<=;j++){

            while(k<=tot&&w[k]-w[j]<pi) k++;

            ans+=(ll)(k-j-)*(k-j-)/*(tot-k+j)*(tot-k+j-)/;

        }

    }

    printf("%I64d\n",ans);

    return ;

}

巴特西

CodeForces - 1025F：Disjoint Triangles （几何）

最新文章

热门文章