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

1楼xiezefan昨天 21:20

你搞那么头函数干什么！···

Re: ACM_cxlove昨天 21:54

回复xiezefann噗。。。不知道。。。n代码不保存，每次都是同样的头文件。。。