10002 - Center of Masses

[Julien Cornebise]

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]

Does anyone have some test cases for this problem?

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

thanks,

sobral

[ithamar]

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.

[ithamar]

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

[turuthok]

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]

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

-turuthok-

[mathijs]

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]

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]

/*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);
}

[szymcio2001]

http://acm.uva.es/board/viewtopic.php?t ... c&start=15

[hujialie]

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

[Subeen]

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]

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]

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]

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