2014
11-29

# Convex

Your task is very simple. You will get the coordinates of n points in a plane. It is guaranteed that there are no three points on a straight line. You can choose any four points from these points to construct a quadrangle. Now, please tell me how many convex quadrangles you can construct.

The first line of input contain an integer z (z ≤ 20), indicating the number of test cases.
For each test case, the first line contain an integer n (4 ≤ n ≤ 700), indicating the number of points. Each of the next n lines contains two integers x and y (-1000000 ≤ x, y ≤ 1000000), indicating the coordinate of corresponding point.

The first line of input contain an integer z (z ≤ 20), indicating the number of test cases.
For each test case, the first line contain an integer n (4 ≤ n ≤ 700), indicating the number of points. Each of the next n lines contains two integers x and y (-1000000 ≤ x, y ≤ 1000000), indicating the coordinate of corresponding point.

2
4
0 0
0 1
1 0
1 1
4
0 0
1 0
0 1
-1 -1

1
0

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll __int64
int T;
ll n;
double x[700],y[700],p[1400],pi=acos(-1.0);
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%I64d",&n);
for(int i=0;i<n;i++)scanf("%lf%lf",x+i,y+i);
ll ans=n*(n-1)*(n-2)*(n-3)/24,C=(n-1)*(n-2)*(n-3)/6;
for(int i=0;i<n;i++)
{
int t=0,top=0;
for(int j=0;j<n;j++)
if(j^i)p[t++]=atan2(y[j]-y[i],x[j]-x[i]);
sort(p,p+t);
for(int j=0;j<n-1;j++)p[t++]=p[j]+pi*2;
//for(int j=0;j<t;j++)printf("%f ",p[j]/pi*180.0);puts("");
ll sum=0;
for(int j=0;j<n-1;j++)
{
while(p[top+1]-p[j]<pi-1e-10/*fuck eps*/)++top;
int cnt=top-j;
if(cnt>=2)sum+=cnt*(cnt-1)/2;
//printf("j=%d,cnt=%d\n",j,cnt);
}
//printf("%lld %lld\n",C,sum);
ans-=C-sum;
}
printf("%I64d\n",ans);
}
}

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

2. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

3. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环