学步园

求多边形的重心（包括凹多边形）

ZJU的模板看了，昨晚在实验室还和大家讨论了下，好不容易看懂了，就是求分割成三角形的重心，然后将每块三角形的面积作为它重心的质量，然后根据点*点的质量/总质量 = 重心，求出。

ZJU的模板求重心用的中线相交法，这题用这个方法的话精度明显损失了好多，WA死了，后来发现这么做实在是太鸡肋了，明明重心就等于三点坐标和/3.。。。><崩溃。。。改了后，顺利A掉。。。

#include <queue><br /> #include <stack><br /> #include <math.h><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <limits.h><br /> #include <string.h><br /> #include <algorithm><br /> using namespace std;<br /> const int MAX = 1000010;<br /> const double eps = 1e-6;<br /> struct point{ double x,y;};<br /> struct line{ point a,b;};<br /> point p[MAX];<br /> double crossProduct(point a,point b,point c)//向量 ac 在 ab 的方向<br /> {<br /> return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);<br /> }<br /> point bary_center(point p[],int n)<br /> {<br /> point ans,t;<br /> double area = 0.0,t2;<br /> ans.x = 0.0; ans.y = 0.0;<br /> for(int i=1; i<n-1; i++)<br /> {<br /> t2 = crossProduct(p[i],p[0],p[i+1])/2.0;<br /> ans.x += (p[0].x + p[i].x + p[i+1].x)*t2;<br /> ans.y += (p[0].y + p[i].y + p[i+1].y)*t2;<br /> area += t2;<br /> }<br /> ans.x /= (3*area);<br /> ans.y /= (3*area);<br /> return ans;<br /> }<br /> int main()<br /> {<br /> int n,ncases;<br /> scanf("%d",&ncases);<br /> while( ncases-- )<br /> {<br /> scanf("%d",&n);<br /> for(int i=0; i<n; i++)<br /> scanf("%lf%lf",&p[i].x,&p[i].y);<br /> point ans = bary_center(p,n);<br /> printf("%.2lf %.2lf/n",ans.x,ans.y);<br /> }<br /> return 0;<br /> }<br />