603
HDU 1115 求多边形重心
一个均匀的多边形重心为 横纵坐标和分别除以六倍的面积。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
using namespace std;
struct point
{
double x,y;
void input()
{
scanf("%lf%lf",&x,&y);
}
void print()
{
printf("%.2f %.2f\n",x,y);
}
};
double cross(point i,point j,point k)
{
return (j.x-i.x)*(k.y-i.y)-(k.x-i.x)*(j.y-i.y);
}
point Gravity(point p[],int n)
{
point O,t;
O.x = O.y = 0;
t.x = t.y = 0;
p[n] = p[0];
double A = 0;
for(int i=0; i<n; i++)
A += cross(O,p[i],p[i+1]);
A /= 2.0;
for(int i=0; i<n; i++)
{
t.x += (p[i].x + p[i+1].x) * cross(O,p[i],p[i+1]);
t.y += (p[i].y + p[i+1].y) * cross(O,p[i],p[i+1]);
}
t.x /= 6*A;
t.y /= 6*A;
return t;
}
point data[1000005];
int main()
{
int t;
int n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0; i<n; i++)data[i].input();
point t=Gravity(data,n);
t.print();
}
return 0;
}
最后更新：2017-04-03 14:53:37