## 10002 - Center of Masses

Moderator: Board moderators

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact: Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Hi fellows

I got WA with this output

Code: Select all

``````printf("%.3lf %.3lf\n",cx,cy);
``````
But I got AC with this

Code: Select all

``````printf("%.3lf %.3lf\n",cx+0.000001,cy+0.000001);
``````

Another stupid precision error.

Hope it helps Yile
New poster
Posts: 17
Joined: Sun Feb 27, 2005 10:36 am
Location: China

### 10002

Code: Select all

``````#include<stdio.h>
#include<math.h>
double getabs(double x)
{
if(x<0)
x*=-1;
return x;
}

double getk(double x1,double y1,double x2,double y2)
{
if(x1==x2)
return 999999999999999.0;
else
return (y1-y2)/(x1-x2);
}

double geta(double x1,double y1,double x2,double y2,double x3,double y3)
{
double k,b,b1,width,height;
if(x1==x2)
return getabs(y1-y2)*getabs(x1-x3)/2.0;
if(x2==x3)
return getabs(y2-y3)*getabs(x2-x1)/2.0;
if(x1==x3)
return getabs(y1-y3)*getabs(x1-x2)/2.0;
k=getk(x1,y1,x2,y2);
b=y1-k*x1;
b1=y3-k*x3;
height=getabs(b-b1)/sqrt(1+k*k);/*?k=tan?????|??????|*cos?*/
width=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
return width*height/2;
}

int main()
{
int n,
i,j;
double x,y,
min,temp,
k1,k2,
center_x,center_y,center1_x,center1_y,
s,s1;
while(scanf("%d",&n),n>2)
{
for(i=0;i<n;i++)
scanf("%lf %lf",&x[i],&y[i]);
min=0;
for(i=1;i<n;i++)
if(y[i]<y[min] || y[i]==y[min] && x[i]<x[min])
min=i;
if(min!=0)
{
temp=y;
y=y[min];
y[min]=temp;
temp=x;
x=x[min];
x[min]=temp;
}
for(i=1;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
k1=getk(x,y,x[i],y[i]);
k2=getk(x,y,x[j],y[j]);
if(k1>=0 && k2>=0 && k1>k2 || k1<0 && k2>=0 || k1<0 && k2<0 && k1>k2)
{
temp=x[i];
x[i]=x[j];
x[j]=temp;
temp=y[i];
y[i]=y[j];
y[j]=temp;
}
}
}
center_x=center_y=s=0;
for(i=1;i<n-1;i++)
{
s1=geta(x,y,x[i],y[i],x[i+1],y[i+1]);
center1_x=(x+x[i]+x[i+1])/3.0;
center1_y=(y+y[i]+y[i+1])/3.0;
center_x=(s*center_x+s1*center1_x)/(s+s1);
center_y=(s*center_y+s1*center1_y)/(s+s1);
s+=s1;
}
printf("%.3lf %.3lf\n",center_x,center_y);
}
return 0;
}``````

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### ooopsi daisy..

Code: Select all

``````if(y[i]<y[min] || y[i]==y[min] && x[i]<x[min])
``````
You declared min as double...
.. but, you can't use 'double variable' as an array index..

.. so change it and try your luck.

Yile
New poster
Posts: 17
Joined: Sun Feb 27, 2005 10:36 am
Location: China
Oh, thanks. If you don't tell me this, maybe I will never notice it. I fix it and get AC. Thank you again.

Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

### Convex hull

When computing the convex hull, be careful with the direction of the ordering. In my case it worked clockwise. Also is convenient to choose the first point of the input as reference.

UWeiss
New poster
Posts: 1
Joined: Fri Dec 02, 2005 12:31 am
>> There is one case, where 3 points are aligned vertically in one line. This case has to be tested manually (depending on what kind of convex hull algorithm is used.

>> Also, as somebody already mentioned you have to negate values between -0.0005 and 0, because -0.000 will be printed, but 0.000 should be printed (imho an error in the sample solution)

Code: Select all

``````if (cx > -0.0005 && cx <= 0)
cx = 0;
if (cy > -0.0005 && cy <= 0)
cy = 0;``````
These were the only things I had to change.

PS: I have tested both. and these fixes are both needed to get AC
PS: the input consists of only Integers (unlike somebody above stated)
PS: using int while summing up the values for the area suffices - no need to use long values (also float suffices for the division afterwards). but using 8Byte representations is better in general - you never know...

migichen
New poster
Posts: 2
Joined: Fri Mar 17, 2006 5:28 am

### Ultima test data

After feeding all the test data provided in this discussing thread but passed all the tests, I still got WA from on-line judge. Finally I found my prb was not precision prb, but an esssential algorithmic bug on rearranging the points.

Earlier in this thread someone mentioned to be aware of aligned points. It may not be a problem until your reference point (to sort out the convex hull) lie in one of the aligned points. See the trivial test data below my program failed in:

Input:

Code: Select all

``````8
0 0
0 1
2 1
2 0
1 0
2 2
1 2
0 2
``````
Output:

Code: Select all

``````1.000 1.000
``````
My program took lowest and left-most point (0,0) as reference and sorted clockwisely by the angle between each other points and the horizontal line. However that could not sort points with the same angle but different distances, and I got my points "rearranged":

0 0
0 2
0 1 (**wrong**)
1 2
2 2
2 1
2 0
1 0

After fixing this prb I got AC See if u have the same prb. CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Hi, thanks to UWeiss , because i think -0.000 was the major bug in my code. and i dont know why my algo only works with double data type. ( i mean if i take the inputs in double its ok, but if i take in int then when needed if i shift to double it doesn't work) does it mean big data in data set?

i ordered the polygon vertices from 1st point and then used the center of mass algo

as it is convex polygon and all the points are the vertex of the polygon so in ordering i used a simple technique:

i take a point and try to find the closest point to that point but i dont go back ( mark the previous points ) so, no clockwise anticlockwise hells
Jalal : AIUB SPARKS

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

### i am getting WA for many times and I am hung

I have no way but to post my code. Anybody there to help , why I am getting WA after 8.898 secs , also pls help how to speed up? I used Graham Scan of CORMEN and read all the previous posts about this prob. My code is a bit long ,but understandable.

..........................................................................................................
#include <stdio.h>
#include <math.h>
#define M_PI acos(-1.0)
long p,top,h,p2;
bool a;
long total;
void Swap(long &x,long &y)
{ long t;
t = x, x = y, y = t;
}

double ang(double x1,double y1,double x2,double y2){
double z;
if(fabs(x1-x2)<1e-9 && fabs(y1-y2) > fabs(x1 -x2) )
return M_PI/2.;
else if(fabs(y1-y2)<1e-9)
return 0.;
else
{

z=atan( (y2-y1)/(x2-x1) ) ;
if(z<0.)
z+= M_PI;
return z;
}
}
long Dis(long i,long j)
{
return ((p-p[j])*(p-p[j]) +
(p-p[j])*(p-p[j]));
}

void AngleSort(long n){
long i,j,prev,tm,dist;
double r,s;
for(i=0;i<n;i++)
a=1;

for(i=1;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(ang(p,p,p,p ) > ang(p,p,p[j],p[j] ) )
{
Swap(p,p[j]);
Swap(p,p[j]);
}

}

}//for
//for elemeniting the same points except the farthest one
for(i=1;i<n-1;i++)
{
dist=Dis(0,i);

prev=i;
for(j=i+1;j<n;j++)
{
r=ang(p,p,p,p[i] ) ;
s= ang(p,p,p[j],p[j]) ;

if(fabs(r-s)<1e-9 ){

if(dist<(tm= Dis(0,j))){

a[prev]=0;
dist =tm;
prev=j;

}
else if(tm<dist){
a[j]=0;

}

}//if
}

}

for(i=0;i<n;i++)
{
p2[i]=p[i];
p2[i]=p[i];
}

j=0;
for(i=0; i<n ; i++)
{
if(a[i]==1)
{
p[j]=p2[i];
p[j]=p2[i];
j++;
}
}
total=j;

}//

long Area(long x1,long y1,long x2,long y2,long x3,long y3)
{

return (x1*(y2-y3)+y1*(x3-x2) +x2*y3-y2*x3);

}
void SetMinimum(long n)
{ long index,i;
index = 0 ;
for(i=1;i<n;i++){
if( p[i] > p[index] ) continue;
else if( p[i] < p[index] )
index = i;
else{
if( p[i] < p[index] )
index = i;
}
}
Swap(p,p[index]);
Swap(p,p[index]);

}
long GrahamScan(long n){
SetMinimum(n);
total=n;
AngleSort(n);
h=p;
h=p;
h=p;
h=p;
h=p;
h=p;
for(i=3;i<total;i++)
{

{
}
}

}

void main(){
long int n,i;
double area,cx,cy;
while(scanf("%ld",&n)==1 && n>=3 )
{

for(i=0;i<n;i++)
{
scanf("%ld%ld",&p[i],&p[i]);
a[i]=1;
}
total =GrahamScan(n);
area=0.;
for(i=1;i<total-1;i++)
{
area+=.5 * fabs(Area(h,h,h[i],h[i],h[i+1],h[i+1]));
}
cx=0.;
cy=0.;
h[total]=h;
h[total]=h;
for(i=0;i<total;i++){
cx+= (h[i] +h[i+1])*(h[i] * h[i+1] -h[i+1] * h[i]);
cy+= (h[i] +h[i+1])*(h[i] * h[i+1] -h[i+1] * h[i]);
}
cx/=(6*area);
cy/=(6*area);
printf("%.3lf %.3lf\n",cx+1e-9,cy+1e-9);

}

}
Life is a challenge.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: i am getting WA for many times and I am hung

Shuvra(CSE-BUET) wrote:I have no way but to post my code. Anybody there to help , why I am getting WA after 8.898 secs , also pls help how to speed up? I used Graham Scan of CORMEN and read all the previous posts about this prob. My code is a bit long ,but understandable.
Try the following:

Code: Select all

``````15
-983 -225
897 -902
-931 918
8 982
940 -845
-865 998
960 205
-959 -746
634 -965
-947 -824
841 912
-184 998
512 -992
-792 -969
-954 485
15
974 -862
-894 974
-752 997
-985 -798
-936 -996
994 -162
623 999
-940 -986
993 -637
984 909
490 -996
996 -456
-991 754
769 992
929 -947
16
989 -242
617 -999
-948 -918
987 150
814 -987
959 -872
-908 993
-802 -985
989 -143
-992 400
925 904
265 992
-958 -787
-774 -992
787 985
-989 829
14
-965 523
-846 -986
-969 -863
904 -966
-999 -42
225 996
-898 863
460 991
-920 835
-695 950
611 -982
972 734
830 919
-804 -1000
6
-517 976
-959 -919
956 294
898 401
-895 501
-906 403
10
664 -798
-855 -957
-811 -976
492 986
-970 -873
961 886
603 -933
-792 743
-689 989
-940 105
7
415 -997
-974 642
-932 953
494 978
909 -948
941 501
-975 -614
15
903 -711
754 978
921 905
978 416
728 -886
-996 982
932 -546
947 -288
906 922
-996 922
-677 -942
-224 -957
866 -865
960 836
-982 -451
10
-923 935
-662 -943
277 -981
976 -532
237 980
770 914
989 756
-901 -472
852 -756
-940 -5
12
-591 -972
668 949
787 -771
-743 876
397 -916
-975 -93
-419 -983
-971 416
939 -684
484 991
949 367
-543 995
2``````
My AC's output:

Code: Select all

``````-21.614 -6.159
-0.552 0.414
-5.803 -0.414
-16.431 -12.760
-239.434 140.009
-53.168 20.817
-8.436 32.275
-10.459 48.319
19.323 30.849
4.952 29.672``````

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

I have just got acc after 2 day's utmost efforts. I have changed my code from O(n*n) to O(n*log(n)) and acc in 1.07 secs.
What can I say for you all that , geometry is very interesting ,don't neglect this type of problems.
Here 3 points can be collinear. Graham scan is must here.
Life is a challenge.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
The following test case has
been posted a lot of time
Try this data
Input :
4
19999999999 1
1 3
3 1
1 2
1
Output :
6666666667.333 1.667
Is this output correct?!

My ACC program outputs:

Code: Select all

``````6666652284.322 1.667
``````
Which is strange...

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
This is very strange and unpleasant. I was trying to solve this problem for some hours on C++, but I got WA for many times, I tried all the fixes offered here but nothing helped. Translated to Pascal - Accepted. But yesterday I have to just translate one problem from Pascal (where I got TLE) to C++ - and it got Accepted. So now I understood, that it's better to solve problems with floating point numbers in Pascal, but other tasks - in C++.
Now I lay me down to sleep...
my profile

Juanito
New poster
Posts: 4
Joined: Thu Sep 18, 2008 5:20 am

### Re: 10002 - Center of Masses

Im getting TLE, im using Gift Wrapping algorithm in java, i though it was enough to pass the tests in 3 seconds, given the low bounds (100 points) should i use graham scan?