Rotational Painting hdu 好的计算几何题！！
/*一道很好的计算几何题啊。题目是求一个多边形能稳定摆放有多少种方式。这道题知道是考查重心。但是一开始没有思路，特别是对凹多边形。原来可以先出重心。然后再求凸包。将所有的四边形补成凸的。这样每一条边就对应着一种放法。然后只要判断重心和这条边的两个角是否为锐角即可。*/#include <stdio.h>#include <iostream>#include <algorithm>#include <cmath>#define maxn 50001using namespace std;struct point{ double x,y;}p[maxn],res[maxn];int n,top;double cross(point a,point b,point o){ return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);}bool cmp(point a,point b){ if(a.x!=b.x) return a.x<b.x; return a.y<b.y;}void graham(){ sort(p,p+n,cmp); res[0] = p[0]; res[1] = p[1]; top = 1; for(int i=2;i<n;i++) { while(top&&cross(p[i],res[top-1],res[top])<=0) --top; res[++top] = p[i]; } int ntop = top; res[++top] = p[n-2]; for(int i=n-3;i>=0;i--) { while(top>ntop&&cross(p[i],res[top-1],res[top])<=0) --top; res[++top] = p[i]; }}bool dmulti(point p0,point p1,point p2){ if(((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y))>0) return true; else return false;}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); double sx=0,sy=0,sum=0,m=0,xi=0,yi=0;//求重心 for(int i=1;i<n-1;i++) { m=cross(p[i],p[i+1],p[0]); xi=p[0].x+p[i].x+p[i+1].x; yi=p[0].y+p[i].y+p[i+1].y; sx+=xi*m; sy+=yi*m; sum+=m; } sx/=sum*3; sy/=sum*3; graham(); point s; s.x=sx,s.y=sy; int step=0; for(int i=0;i<top;i++) { if(dmulti(res[i],res[(i+1)%top],s)&&dmulti(res[(i+1)%top],res[i],s)) step++; } printf("%d\n",step); } return 0;}