## 10002 - Center of Masses

Moderator: Board moderators

bolster
New poster
Posts: 16
Joined: Tue Oct 30, 2001 2:00 am

### 10002 - Center of Masses

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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
find the CONVEX HULL first ..
bolster
New poster
Posts: 16
Joined: Tue Oct 30, 2001 2:00 am
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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
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
New poster
Posts: 16
Joined: Tue Oct 30, 2001 2:00 am
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
New poster
Posts: 16
Joined: Tue Oct 30, 2001 2:00 am
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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Does anyone know where the critical point is?
a little disappointed on this problem...
wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
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
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:
??
Last edited by Jalal on Tue Jun 18, 2002 9:53 pm, edited 1 time in total.
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
The problem description clearly says what to do in the case m<3.
Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:

### 10002

/* @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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

### I thougt it was the definition ...?

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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
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.