10002  Center of Masses
Moderator: Board moderators

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
Test cases
Does anyone have some test cases for this problem?
I just can't find what is wrong on my algorithm....
thanks,
sobral
I just can't find what is wrong on my algorithm....
thanks,
sobral
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.
Forget this sentence in the problem statement if you want to solve this problem.
Hope this can help.No three points are aligned in any polygon.
Those Who Don't Know History are doomed to repeat it
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

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
10002  Center of Mass
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 polygonpoints 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 weightedsum to get the centroid.
Is there any trick in this problem that I'm not aware of ... ???
Thanks,
turuthok
Is there any trick in this problem that I'm not aware of ... ???
Thanks,
turuthok
 mathijs
 New poster
 Posts: 7
 Joined: Tue Mar 04, 2003 5:15 pm
 Location: Groningen, The Netherlands
 Contact:
Strange inputs?
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?
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?
10002
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==ik==j)k++;
t1=(y[j]y)*x[k]+(xx[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==ik==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]
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==ik==j)k++;
t1=(y[j]y)*x[k]+(xx[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==ik==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]
still wrong answer!
/*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<=n1;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);
}
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<=n1;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);
}

 New poster
 Posts: 38
 Joined: Mon Dec 09, 2002 1:53 pm
 Location: Poznan, Poland
What do you mean by this address?
I've watched it,but still can't find where is wrong.
I got WA in this problem. Is there any problem with my algorithm / formula ? plz help me.
This is what I did:
and you can give me some critical input/output to test my program with.
Thanks.
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)
Thanks.
Correct definition of a center of masses?!
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]
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]
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
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