题目描述：给你n个点（4~700）， 问你能够成多少个不同的凸四边形。
求出所有凹包的个数，然后用总数C(n, 4)减去凹包的个数，就是答案。
依次枚举每个点i，看看其它点能够成多少个包括点i的三角形，就是以这个点为中心的凹包的个数。
找三角形也要一定的技巧，也是通过逆向思维：找出有多少个三角形不包括点i，然后用总三角形个数C(n – 1, 3) – 以这个点为中心的凹包的个数。
注意到，如果3个点不能圈住中心点，则必然是存在一条通过中心点的直线，使得这三个点都在直线的同侧。利用这个形式，我们用如下方法寻找三角形：
1：以中心点为中心，对剩余n-1个点极角排序。
2：依次处理排序后的n-1个点，对于每一个点i，依次往后扫描，找到第一个点j，是j和i的夹角大于180度。
3：那么点i + 1到点j – 1的所有点都可以和点i构成不包括中心点的三角形。个数是C(j – i – 1, 2)
#include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; #define LL long long #define eps 1e-8 double pi=2*asin(1); struct point { double x,y; }p[705]; double A[1705]; LL cal(int n,int m) { LL ret=1; for(int i=n;i>n-m;i--) ret=(LL)(ret*i); for(int i=1;i<=m;i++) ret/=i; return ret; } int main() { int n,T,i,j; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); LL ans=cal(n,4)-n*cal(n-1,3); for(i=0;i<n;i++) { int m=0,k=1; for(j=0;j<n;j++) //极角排序 { if(i==j) continue; A[m++]=atan2(p[j].y-p[i].y,p[j].x-p[i].x); if(A[m-1]<eps) A[m-1]+=2*pi; } sort(A,A+m); for(j=m;j<2*m;j++) A[j]=A[j-m]+2*pi; for(j=0;j<m&&k<2*m;j++) { while(k<2*m&&A[k]-A[j]<pi) k++; if(k-j-1>1) ans+=cal(k-j-1,2); } } printf("%lld\n",ans); } return 0; }
原文：http://www.cnblogs.com/zuferj115/p/5221913.html