Question

多边形重心问题acm我的怎么是wrong answer？

http://acm.nyist.net/JudgeOnline/problem.php?pid=3
样例过了。。它的精确还要限制吗……谢谢了，哪个错了。。我用的是多边形面积公式，重心坐标公式，感觉没错。
#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
struct point
{
double x;
double y;
};
int main()
{
int n,m,i;
point a[10000];
cin>>n;
while(n--)
{
double area=0;
double x1=0;
double y1=0;
cin>>m;
for(i=0;i<m;i++)
cin>>a[i].x>>a[i].y;
for(i=0;i<=m-2;i++)
area+=a[i].x*a[i+1].y;
for(i=1;i<=m-1;i++)
area-=a[i].x*a[i-1].y;
area=area+a[m-1].x*a[0].y-a[0].x*a[m-1].y;
area=fabs(area)/2;
for(i=1;i<=m-2;i++)
x1+=(a[0].x+a[i].x+a[i+1].x)/3*(fabs(a[0].x*a[i].y+a[i].x*a[i+1].y+a[i+1].x*a[0].y-a[i].x*a[0].y-a[i+1].x*a[i].y-a[0].x*a[i+1].y)/2);
for(i=1;i<=m-2;i++)
y1+=(a[0].y+a[i].y+a[i+1].y)/3*(fabs(a[0].x*a[i].y+a[i].x*a[i+1].y+a[i+1].x*a[0].y-a[i].x*a[0].y-a[i+1].x*a[i].y-a[0].x*a[i+1].y)/2);
x1=x1/area;
y1=y1/area;
if(area<0.00001)
printf("0.000 0.000\n");
else
{ printf("%.3lf ",area);
printf("%.3lf\n",x1+y1);}
}
return 0;
}

Answer 1

#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
struct point {
	double x;
	double y;
};
int main() {
	int n, m, i;
	point a[10000];
	cin >> n;
	while (n--) {
		double area = 0;
		double x1 = 0;
		double y1 = 0;
		cin >> m;
		for (i = 0; i < m; i++) {
			cin >> a[i].x >> a[i].y;
		}
		for (i = 1; i <= m - 2; i++) {
			double temp = ((a[i].x - a[0].x) * (a[i + 1].y - a[0].y) 
						 - (a[i].y - a[0].y) * (a[i + 1].x - a[0].x)) / 2.0;
			x1 += (a[0].x + a[i].x + a[i + 1].x) / 3.0 * temp;
			y1 += (a[0].y + a[i].y + a[i + 1].y) / 3.0 * temp;
			area += temp;
		}
		x1 = x1 / area;
		y1 = y1 / area;
		area = fabs(area);
		if (area < 1e-6)
			printf("0.000 0.000\n");
		else {
			printf("%.3f ", area);
			printf("%.3f\n", x1 + y1);
		}
	}
	return 0;
}

 

计算重心的时候，面积部分不应该带fabs

追问

哦。。谢谢，还有那个精确度是怎么回事呢。。

追答

你只要x1和y1里面的两个fabs去掉，然后取反就可以了

追问

嗯嗯，我已经交过了。。对了。只不过还要写精确度。。

追答

面积太小就当0吧，其实我也觉得这个不太好，万一面积真的可以很小。。。。这个时候重心位置不是0