HDU 3629 Convex（10年天津，计算几何）
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：给出N个点，选出4个点组成凸多边形的有多少种
http://acm.hdu.edu.cn/showproblem.php?pid=3629
C(N,4)的枚举必挂。
哎还是太弱了，看了别人的做法
因为只考虑4个点，凹包的情况是，3个点组成的三角形内部有一个点
那么我们就用所有的情况，减掉凹包
而对于凹包还不好求，可以考虑选出3个点，另外一个点不在三角形内部，也就是三个点在过另外一个点的直线的同侧。那么我们就可以枚举那一个顶点，也就是可能在内部的点。
然后通过其它点的极角排序，找到两端夹角恰好大于pi的情况，那么从中间选出两个点加上端点
还有一些细节需要处理，下面这篇博客说得比较详细
http://blog.sina.com.cn/s/blog_64675f540100ksug.html
#include<iostream>#include<fstream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<set>#include<map>#include<queue>#include<stack>#include<string>#include<vector>#include<ctime>#include<sstream>#include<cassert>#define LL long long#define eps 1e-7#define zero(a) fabs(a)<eps#define inf 1<<30#define N 20#define pi acos(-1.0)#define pb(a) push_back(a)using namespace std;struct Point{ double x,y;}p[700];int n;double angle[700];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 t; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int 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(int i=0;i<n;i++){ int m=0,k=1; for(int j=0;j<n;j++){ if(i==j) continue; angle[m++]=atan2(p[j].y-p[i].y,p[j].x-p[i].x); if(angle[m-1]<eps) angle[m-1]+=pi; } sort(angle,angle+m); for(int j=m;j<2*m;j++) angle[j]=angle[j-m]+2*pi; for(int j=0;j<m&&k<2*m;j++){ while(k<2*m&&angle[k]-angle[j]<pi) k++; if(k-j-1>1) ans+=cal(k-j-1,2); } } printf("%I64d\n",ans); } return 0;}