10002 - Center of Masses

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10002 - Center of Masses

Post by bolster » Thu Nov 22, 2001 7:47 am

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

Post by Even » Thu Nov 22, 2001 3:22 pm

find the CONVEX HULL first ..

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

Post by bolster » Thu Nov 22, 2001 5:55 pm

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

Post by Even » Fri Nov 23, 2001 2:23 pm

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

Post by bolster » Fri Nov 23, 2001 4:52 pm

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 :smile: )

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

Post by bolster » Sat Dec 01, 2001 6:57 pm

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

Post by Even » Sun Dec 02, 2001 4:40 pm

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

Post by LittleJohn » Wed Apr 03, 2002 2:35 pm

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

Post by wyvmak » Mon Apr 29, 2002 4:15 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
Location: BANGLADESH
Contact:

Post by Jalal » Sun Jun 02, 2002 8:49 pm

??
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:

Post by Stefan Pochmann » Sun Jun 02, 2002 11:39 pm

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
Location: BANGLADESH
Contact:

10002

Post by Jalal » Tue Jun 18, 2002 9:50 pm

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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Wed Jun 19, 2002 3:35 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 ...?

Post by Julien Cornebise » Wed Jun 26, 2002 11:55 am

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:

Post by 10153EN » Wed Jun 26, 2002 12:19 pm

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.

Post Reply

Return to “Volume 100 (10000-10099)”