/*********************************
* 日期:2011-3-7
* 作者:SJF
* 题号:杭电1065
* 题目:I Think I Need a Houseboat
* 结果:AC
* 总结:有多边形重心公式,需要知道每个顶点坐标,令面积为area,则
area=sum(X[i]*Y[i+1]-X[i+1]*Y[i])
x=sum( (X[i]*Y[i+1]-X[i+1]*Y[i]) * (Xi+X(i+1)) / (6*area) )
y=sum( (X[i]*Y[i+1]-X[i+1]*Y[i]) * (Yi+Y(i+1)) / (6*area) )
x,y为重心坐标;
**********************************/
#include<stdio.h>
#define MAX 1000010
typedef struct
{
double x;
double y;
}Point;
Point point[MAX];
void Gravity(int n)
{
int i;
double area=0,x=0,y=0;
point[n]=point[0];
for(i=0;i<n;i++)
{
area+=((point[i].x)*(point[i+1].y)-(point[i+1].x)*(point[i].y))/2;
x+=((point[i].x)*(point[i+1].y)-(point[i+1].x)*(point[i].y))*(point[i].x+point[i+1].x);
y+=((point[i].x)*(point[i+1].y)-(point[i+1].x)*(point[i].y))*(point[i].y+point[i+1].y);
}
printf("%.2lf %.2lf\n",x/(6*area),y/(6*area));
}
int main()
{
int T,n;
while(scanf("%d",&T)!=EOF)
{
while(T--)
{
int i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%lf %lf",&point[i].x,&point[i].y);
}
Gravity(n);
}
}
}
分享到:
相关推荐
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
I Think I Need a Houseboat Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 41126 Accepted: 16537 Description Fred Mapper is considering purchasing some land in Louisiana to build his ...
1049 I Think I Need a Houseboat 简单题 1028 Flip and Shift 简单题,可以DP/BFS/……,但是实际上有数学方法可直接判断出来 1026 Modular multiplication of polynomials 简单题,有比较简单的好算法 1307 ...
北大ACM 1005题 我的答案呵呵 高手们帮忙看看呵呵 菜鸟们 学习呵呵
1049 I Think I Need a Houseboat 简单题 1028 Flip and Shift 简单题,可以DP/BFS/……,但是实际上有数学方法可直接判断出来 1026 Modular multiplication of polynomials 简单题,有比较简单的好算法 1307 ...
10.Dexter need help 11.Double 12.Easy problem 13.Favorite number 14.Graveyard 15.Hailstone 16.Hanoi Ⅱ 17.Houseboat 18.Music Composer 19.Redistribute wealth 20.Road trip 21.Scoring 22.Specialized ...
Dexter need help;Checksum algorithm;Graveyard;Hanoi II;Houseboat;Sum of Consecutive;Arithmetic Progressions;Redistribute wealth;Scoring;Specialized Numbers;操场训练;最长回文子串;寻找规律;...