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

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Wed Jun 26, 2002 3:00 pm

That's what I've done, but it seems not deeply enought. Well, anyway, I'll try this one another day : I'm not good at all at geometrical problems :)

sobral
New poster
Posts: 2
Joined: Fri Jul 12, 2002 3:51 pm

Test cases

Post by sobral » Sat Jul 13, 2002 7:06 pm

Does anyone have some test cases for this problem?

I just can't find what is wrong on my algorithm....

thanks,

sobral

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar » Thu Sep 19, 2002 5:06 pm

I am tired of problem whose data sets does not correspond to the problem description. This is one of them.

Forget this sentence in the problem statement if you want to solve this problem.
No three points are aligned in any polygon.
Hope this can help.
Those Who Don't Know History are doomed to repeat it

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar » Thu Sep 19, 2002 5:14 pm

Some test cases to think about it.

Code: Select all

    Input 
    4
    1 1
    1 3
    3 1
    1 2

    Output
    1.667 1.667
Those Who Don't Know History are doomed to repeat it

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

10002 - Center of Mass

Post by turuthok » Sat Feb 01, 2003 12:39 am

Hello all, could you guys help me on this 10002 - Center of Mass problem. What I did was first to decide the ordering of the polygon-points that leads to computing the area of the polygon based on the ordering of points. Then the next thing is to apply some kind of weighted-sum to get the centroid.

Is there any trick in this problem that I'm not aware of ... ???

Thanks,

-turuthok-

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Tue Feb 04, 2003 6:47 am

Found the culprit. Got a bad usage of java.text.DecimalFormat class.

-turuthok-

User avatar
mathijs
New poster
Posts: 7
Joined: Tue Mar 04, 2003 5:15 pm
Location: Groningen, The Netherlands
Contact:

Strange inputs?

Post by mathijs » Thu Mar 06, 2003 5:10 pm

I solved the problem by choosing one (x,y) value, sorting all points by angle around that point, making triangles consisting of two subsequent vertices of the polygon and (x,y) and calculating the center of mass.

The funny thing is: I first used the average of all points as the (x,y) value and it didn't work (WA). After that I tried using the first point listed in the input and it did work. But I can't imagine a case in which it would matter (as a matter of fact, I runned both algorithms for half an hour on random input and they never disagreed on the answer).

Could it be a small precision error?

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

10002

Post by hujialie » Fri Apr 18, 2003 11:18 am

Why always Wrong Answer?I have noticed the alignment of more than 3 points.

int n;
int x[101],y[101];
double s,sx,sy;

double area1ij(int i,int j)
{
double area;
area=0.5*(x[1]*y+x*y[j]+x[j]*y[1]-x[1]*y[j]-x*y[1]-x[j]*y);
if(area<0)area=-area;
return(area);
}

int isedge(int i,int j)
{
int k=1;
long t1,t2;
while(k==i||k==j)k++;
t1=(y[j]-y)*x[k]+(x-x[j])*y[k]+(y*x[j]-x*y[j]);
if((t1==0)&&((x[k]-x)*(x[k]-x[j])<0))return(0);
do
{
do
{
k++;
}while(k==i||k==j);
if(k<=n)
{
t2=(y[j]-y)*x[k]+(x[i]-x[j])*y[k]+(y[i]*x[j]-x[i]*y[j]);
if(t2==0&&((x[k]-x[i])*(x[k]-x[j])<0))return(0);
if(t1*t2<0)return(0);
}
}while(k<n);
return(1);
}

int main()
{
int i,j,k;
double temp;
scanf("%d",&n);
while(n>=3)
{
s=0;sx=0;sy=0;
for(i=1;i<=n;i++)scanf("%d %d",&x[i],&y[i]);
i=1;k=1;
if(n>3)
{
do
{
for(j=1;j<=n;j++)
{
if((j!=k)&&(j!=i)&&(isedge(i,j)==1))
{
if((i!=1)&&(j!=1))
{
temp=area1ij(i,j);
s=s+temp;
sx=sx+temp*(x[1]+x[i]+x[j])/3;
sy=sy+temp*(y[1]+y[i]+y[j])/3;
}
k=i;
i=j;
break;
}
}
}while(i!=1);
printf("%.3f %.3f\n",sx/s,sy/s);
}
else
{
sx=x[1]+x[2]+x[3];sy=y[1]+y[2]+y[3];
printf("%.3f %.3f\n",sx/3.0,sy/3.0);
}
scanf("%d",&n);
}
return(0);
}[/c]

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

still wrong answer!

Post by hujialie » Sat May 17, 2003 4:43 pm

/*I have changed my code into a relatively simple one,but still wrong answer.I have checked my programme with an AC one,but can't find
any output different.Please point out my mistake,or give some input
data which this programme will produce a wrong answer,I'll be very
thankful.*/


int n;
double x[101],y[101];

void swap(int i,int j) /*swap the two points*/
{
double temp;
temp=x;x=x[j];x[j]=temp;
temp=y;y=y[j];y[j]=temp;
}

double area1ij(int i,int j)/*this function returns the area of triangle consisting of point 1,i,j*/
{
double area;
area=0.5*(x[1]*y+x*y[j]+x[j]*y[1]-x[1]*y[j]-x*y[1]-x[j]*y);
if(area<0)area=-area;
return(area);
}

int main()
{
int i,j;
int lowleft;
double temp,s,sx,sy;
scanf("%d",&n);
while(n>=3)
{
s=0;sx=0;sy=0;
lowleft=1;
for(i=1;i<=n;i++)scanf("%lf%lf",&x,&y);
for(i=2;i<=n;i++)if(y[i]<y[lowleft]||(y[i]==y[lowleft]&&x[i]<x[lowleft]))lowleft=i;
swap(1,lowleft); /*get the lowest and leftest point*/
for(i=2;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if((x[i]-x[1])*(y[j]-y[1])<(x[j]-x[1])*(y[i]-y[1]))
{
swap(i,j);
}
}
} /*sort according to the inclination of the line connecting point lowleft and i,thus to get a polygon crust*/
for(i=2;i<=n-1;i++)
{
temp=area1ij(i,i+1);
s=s+temp;
sx=sx+temp*(x[1]+x[i]+x[i+1])/3;
sy=sy+temp*(y[1]+y[i]+y[i+1])/3;
} /*dividing the polygon into triangles and computing*/
printf("%.3f %.3f\n",sx/s,sy/s);
scanf("%d",&n);
}
return(0);
}

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Post by szymcio2001 » Sun May 25, 2003 11:25 am


hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

What do you mean by this address?

Post by hujialie » Mon May 26, 2003 1:01 pm

I've watched it,but still can't find where is wrong.

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Tue Sep 30, 2003 9:06 am

I got WA in this problem. Is there any problem with my algorithm / formula ? plz help me.
This is what I did:

Code: Select all

1. Find the Convex Hull of the Polygon
2. Get the area of the Polygon
3. Using the formula below find the center (X, Y):

      X = SUM[(Xi + Xi+1) * (Xi * Yi+1 - Xi+1 * Yi)] / (6 * Area)
      Y = SUM[(Yi + Yi+1) * (Xi * Yi+1 - Xi+1 * Yi)] / (6 * Area)
and you can give me some critical input/output to test my program with.
Thanks.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Correct definition of a center of masses?!

Post by BiK » Mon Nov 03, 2003 8:07 pm

Hi to all (anti-)fans of Computational Geometry.

I "asked" mathworld.wolfram.com about the definition of "center of masses" and this is what he "told" me:
(http://mathworld.wolfram.com/GeometricCentroid.html)

The centroid of a set of n point masses m located at positions x is:

(Sum(i=1 to n) (m*x)) / Sum(i=1 to n) (m)

which, if all masses are equal, simplifies to:

(Sum(i=1 to n) x) / n.

This is also the definition I learned at school 10 years ago. But it seems to be different for the online judge...

Has the center of masses changed over the years?! javascript:emoticon(':-?')

Can anybody give me "the right" definition, please?

10x in advance!

:-? [/quote]

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Sun Nov 09, 2003 3:06 pm

bolster wrote:2) Sometimes, "-0.000" is probably displayed for small numbers that get rounded off, so must add some small value to all output.
This trick did it for me. I added some constant epsilon = 1e-15 to the final answer, and I got accepted right away.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Sun Nov 09, 2003 3:12 pm

Btw, the definition of "Center of mass" is quite easy: Suppose you make the polygon out of wood (make it massive), and try to balance it on the tip of your finger. The center of mass is the single point where it will not fall off your finger.
I think many people here are confused with the center of mass of a number of mass points. If you apply the formulas mentioned above, what you are really calculating is the center of mass in the case that all mass of the polygon is concentrated around the vertices (with each vertex having equal mass). However, in this problem the mass is distributed equally on the polygon.
If you still want to apply the "simple formula" for the center of mass, you can consider the massive polygon as a large number of mass points distributed equally on the polygon. But to get the correct answer, you will have to take the limit in which the number of points goes to infinity, and then your sum becomes an integral.

I hope this helps

Post Reply

Return to “Volume 100 (10000-10099)”