Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
100万个点我开了个10万的数组居然过了。。。按黑书的做法求重心:将多边形划分成多个三角形,利用三角形的重心公式。 自己阅读理解: void getcentroid(point p[],int n,point &c){ double tx=0,ty=0; double a=getarea(p,n); int i; //p[n]=p[0];! for(i=0;i<n;i++) tx=tx+(p[i].x+p[i+1].x)*(p[i].x*p[i+1].y-p[i+1].x*p[i].y); for(i=0;i<n;i++) ty=ty+(p[i].y+p[i+1].y)*(p[i].x*p[i+1].y-p[i+1].x*p[i].y); c.x=tx/(6.0*a);c.y=ty/(6.0*a); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator