hdu1115 Lifting the Stone（求多边形重心）

/*
题目描述：
有一个密度均匀的平面N多边形(3 <= N <= 1000000)，可能凹也可能凸，但没有边相交叉，
另外已知N个有序(顺时针或逆时针)顶点的坐标值，第j个顶点坐标为（Xi ， Yi ），且满
足 (|Xi|, |Yi| <= 20000)，求这个平面多边形的重心。

解题过程：
从第1个顶点出发，分别连接第i, i+1个顶点组成三角形Ti,1 < i < n,
一共n-2个三角形正好是多连形的一个划分，分别求出每个三角形的面积Si，
总面积为各个面积相加
根据物理学知识得：n个点(xi,yi)每个重量是mi,则重心是
X = (x1*M1+x2*M2+...+xn*Mn) / (M1+M2+....+Mn)
Y = (y1*M1+y2*M2+...+yn*Mn) / (M1+M2+....+Mn)
另个需要用的知识有：
已知3点求三角形的面积，设三点分别为p[0].x, p[0].y p[1].x, p[1].y p[1].x, p[1].y
面积s =[ p[0].x*p[1].y-p[1].x*p[0].y + p[1].x*p[2].y-p[2].x*p[1].y + p[2].x*p[0].y-p[0].x*p[2].y ] / 2 ,

这里的面积是指有向面积，当三个顶点呈逆时针排列，有向面积为正。逆时针，面积为负。三点共线，面积为零。
这是这3个点是逆时针的值，顺时针取负。
已知3点求重心，x = (p[0].x+p[1].x+p[2].x)/3.0 , y = (p[0].y+p[1].y+p[2].y)/3.0
另外在求解的过程中，不需要考虑点的输入顺序是顺时针还是逆时针，相除后就抵消了，
还要注意 一点是不必在求每个小三角形的重心时都除以3，可以在最后除一下

*/

#include<stdio.h>
#include<math.h>
int n;
double x[1000005],y[1000005],ansx,ansy,answ;
double calw(int s)
{
	double ans;
	ans=x[0]*y[s]+x[s]*y[s+1]+x[s+1]*y[0]
	     -x[s]*y[0]-x[0]*y[s+1]-x[s+1]*y[s];
    return ans;
}
void calans()
{
	int i,j;
	double xx,yy,ww;
	ansx=ansy=answ=0;
	for(i=1;i<n-1;i++)
	{
	   xx=(x[0]+x[i]+x[i+1]);//刚开始是这里除以三，wa了
	   yy=(y[0]+y[i]+y[i+1]);
	   ww=calw(i);	
	   ansx+=xx*ww;
	   ansy+=yy*ww;
	   answ+=ww;
	}
	ansx/=answ;
	ansy/=answ;
	printf("%.2f %.2f\n",ansx/3,ansy/3);//之后改成这里除以三，就ac了，why？？
}
int main()
{
	int i,j,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
		  scanf("%lf%lf",&x[i],&y[i]);
        calans();
	}
	return 0;
}