ACM12

多边形重心问题

时间限制：3000 ms  |  内存限制：65535 KB

难度：5

描述 在某个多边形上，取n个点，这n个点顺序给出，按照给出顺序将相邻的点用直线连接， （第一个和最后一个连接），所有线段不和其他线段相交，但是可以重合，可得到一个多边形或一条线段或一个多边形和一个线段的连接后的图形；

如果是一条线段,我们定义面积为0，重心坐标为（0,0）.现在求给出的点集组成的图形的面积和重心横纵坐标的和；

输入第一行有一个整数0<n<11,表示有n组数据；

每组数据第一行有一个整数m<10000,表示有这个多边形有m个顶点；输出输出每个多边形的面积、重心横纵坐标的和，小数点后保留三位；样例输入3

3

0 1

0 2

0 3

3

1 1

0 0

0 1

4

1 1

0 0

0 0.5

0 1

样例输出0.000 0.000

0.500 1.000

0.500 1.000

#include<iostream>

#include<cmath>

using namespace std;

#define INF 0.0000001

int main()

{

int n,m;

int i;

double x[10010],y[10010];

double sum,dots;

cin>>m;

while(m--)

{

//赋初值

dots = sum = 0;

//输入数据

cin>>n;

for(i=0; i<n; i++)

{

cin>>x[i]>>y[i];

}

//计算

for(i=1; i<=n; i++)

{

//本题重点

//分割成若干三角形求

double temp = (y[i-1]*x[i%n] - y[i%n]*x[i-1]) / 2.0;//临时面积

sum += temp;

//物理知识求重心（貌似是高数里的）

dots += temp * (x[i%n] + x[i-1] + y[i%n] + y[i-1]) / 3.0;

}

cout.precision(3);

if(sum < INF)//如果改为sum == 0 会增加时间的消耗

{

cout<< "0.000" <<' '<< "0.000" <<endl;

}

else

{

cout<<fixed<< fabs(sum) <<' '<< dots/sum <<endl;

}

}

return 0;

}

#include <stdio.h>

#include <math.h>

inline double g(double x1,double y1,double x2,double y2,double x3,double y3)

{ 

    return (x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)/2;

}

int main()

{ 

    int n,m;  scanf("%i",&n); 

while(n--){ 

scanf("%i",&m); 

m-=2; 

double x1,y1,x,y,xn,yn,gsx=0,gsy=0,s=0,cs=0; 

scanf("%lf%lf%lf%lf",&x1,&y1,&x,&y); 

while(m--)  {   

  scanf("%lf%lf",&xn,&yn);   

  s+=(cs=g(x1,y1,x,y,xn,yn));   

  gsx+=(x1+x+xn)*cs/3;   

  gsy+=(y1+y+yn)*cs/3;   

  x=xn;   

  y=yn; 

} 

printf("%.3f %.3f\n",fabsf(s),(s==0?0.0:fabsf((gsx+gsy)/s))); 

}

}