http://acm.hdu.edu.cn/showproblem.php?pid=1115
计算多边形内心的模板题
思路
从第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> struct node { double x,y; }p[1000010]; double area(int a,int b,int c) { return (p[b].x-p[a].x)*(p[c].y-p[a].y)-(p[b].y-p[a].y)*(p[c].x-p[a].x); } int main() { int t,n,i; double sumx,sumy,ar,x,y,sumarea; scanf("%d",&t); while(t--) { scanf("%d",&n); sumx=sumy=sumarea=0; for(i=0;i<n;i++) { scanf("%lf%lf",&p[i].x,&p[i].y); if(i>1) { x=p[0].x+p[i-1].x+p[i].x; y=p[0].y+p[i-1].y+p[i].y; ar=area(0,i-1,i); sumarea+=ar; sumx+=x*ar; sumy+=y*ar; } } printf("%.2lf %.2lf ",sumx/sumarea/3.0,sumy/sumarea/3.0); } return 0; }