10002 - Center of Masses

[bolster]

Hi,

What am I doing wrong here?

1) Find point of lowest 'y' coord
2) sort the other points according to polar coordinates (angle), relative to the first point
3) Apply the following algo:

Code: Select all

a = cx = cy = 0;
for(i=1; i < n-1; ++i) {
  aa = cross(p[i].x-p[0].x,p[i].y-p[0].y, p[i+1].x-p[0].x,p[i+1].y-p[0].y);
  xa = (p[0].x + p[i].x + p[i+1].x)/3;
  ya = (p[0].y + p[i].y + p[i+1].y)/3;
  cx = (aa*xa + a*cx)/(aa + a);
  cy = (aa*ya + a*cy)/(aa + a);
  a += aa;
}
printf("%.3lf %.3lfn", cx, cy);

This obviously works with the sample input, and several other test cases. I'm just doing a basic triangulation and adjusting the (cx, cy) as I go along. Are there any special cases I should worry about?

thanks,

bolster

<font size=-1>[ This Message was edited by: bolster on 2001-11-22 06:48 ]</font>

[Even]

find the CONVEX HULL first ..

[bolster]

I thought about finding the convex hull first, but since it's a convex polygon, it shouldn't matter. If you find the lowest point in the set, and sort the others in increasing polar angles, with respect to that lowest point, then since it's convex, you will have the points in counter-clockwise order, will you not? Is there a counterexample you can give me, please?

[Even]

mm... although it says that input will be a convex hull ...

but I suggest that you should find the convex hull first...

you can try it ....

if it still WA and I will give you another suggestion.

[bolster]

Alright =)

I'll get to work on that later, thanks. (heh I hate geometry problems... In many cases, it's always some stupid meaningless roundoff error from doing the calculation in a different manner... they should allow a +/- 0.005 or something )

[bolster]

fyi:

Here is what the problem was (it had nothing do to with hull):

1) you have to worry about the case where several points are colinear (aa is zero)

2) Sometimes, "-0.000" is probably displayed for small numbers that get rounded off, so must add some small value to all output.

b

[Even]

hello~
my definition of CONVEX HULL contains no co-line...
and there indeed has floating error...
my method doesn't div 3 or "area" in for loop ...
I div 3*area when print the answer ....

[LittleJohn]

Does anyone know where the critical point is?
a little disappointed on this problem...

[wyvmak]

For my personal experience, I got headache on this problem for quite a long period of time too, until I realized that the input points are not necessarily integers, ie. input points can be floating point numbers. I hope that would help, if you haven't realized this yet.

[Jalal]

??

[Stefan Pochmann]

The problem description clearly says what to do in the case m<3.

[Jalal]

Then wt about this?

/* @JUDGE_ID: 17544MJ 10002 C++ */
#include<stdio.h>
void main()
{
long i, n;


for(;scanf("%ld", &n)==1;)
{

if(n>=3)
{


double sum1 = 0, sum2 = 0, num1, num2, x, y;

for(i=0; i < 2*n; ++i)
{
if(i%2==0)
{
scanf("%lf", &num1);
sum1 = sum1 + num1;
}

else
{
scanf("%lf", &num2);
sum2 = sum2 + num2;
}


}


x = sum1 / n;
y = sum2 / n;

printf("%0.3lf %0.3lf\n", x, y);
}

}

}

/* @END_OF_SOURCE_CODE */

[wyvmak]

I'm afraid your code cannot even get the exact output from the sample input.

That's not the way it works. ie. average of coordinates cannot get you centre of mass. In general, average of coordinates works only when n=3, if my understanding is correct.

[Julien Cornebise]

I thought that the defintion of center of mass was "the average of the coordinates". As it appears not to be, then what is it ?

[10153EN]

I think your definition of centre of mass is not correct for all case, just correct for triangles.

You can search in Google or Yahoo and you will find the definition of "centre of mass" of a polygon.