
10002 - Center of Masses
Moderator: Board moderators
-
- Experienced poster
- Posts: 131
- Joined: Sat Jul 17, 2004 4:09 am
- Location: Lima, Per
Hi fellows
I got WA with this output
But I got AC with this
Another stupid precision error.
Hope it helps
I got WA with this output
Code: Select all
printf("%.3lf %.3lf\n",cx,cy);
Code: Select all
printf("%.3lf %.3lf\n",cx+0.000001,cy+0.000001);
Another stupid precision error.
Hope it helps

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[100],y[100],
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[0];
y[0]=y[min];
y[min]=temp;
temp=x[0];
x[0]=x[min];
x[min]=temp;
}
for(i=1;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
k1=getk(x[0],y[0],x[i],y[i]);
k2=getk(x[0],y[0],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[0],y[0],x[i],y[i],x[i+1],y[i+1]);
center1_x=(x[0]+x[i]+x[i+1])/3.0;
center1_y=(y[0]+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;
}
ooopsi daisy..
A part of your code.
You declared min as double...
.. but, you can't use 'double variable' as an array index..
.. so change it and try your luck.
Code: Select all
if(y[i]<y[min] || y[i]==y[min] && x[i]<x[min])
.. but, you can't use 'double variable' as an array index..
.. so change it and try your luck.
- 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.
>> 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)
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...
>> 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;
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...
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:
Output:
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.
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
Code: Select all
1.000 1.000
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
- Location: AIUB, Bangladesh
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
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
-
- 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[120][2],top[120],h[120][2],p2[120][2];
bool a[120];
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[0]-p[j][0])*(p[0]-p[j][0]) +
(p[1]-p[j][1])*(p[1]-p[j][1]));
}
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[0][0],p[0][1],p[0],p[1] ) > ang(p[0][0],p[0][1],p[j][0],p[j][1] ) )
{
Swap(p[0],p[j][0]);
Swap(p[1],p[j][1]);
}
}
}//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[0][0],p[0][1],p[0],p[i][1] ) ;
s= ang(p[0][0],p[0][1],p[j][0],p[j][1]) ;
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][0]=p[i][0];
p2[i][1]=p[i][1];
}
j=0;
for(i=0; i<n ; i++)
{
if(a[i]==1)
{
p[j][0]=p2[i][0];
p[j][1]=p2[i][1];
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][1] > p[index][1] ) continue;
else if( p[i][1] < p[index][1] )
index = i;
else{
if( p[i][0] < p[index][0] )
index = i;
}
}
Swap(p[0][0],p[index][0]);
Swap(p[0][1],p[index][1]);
}
long GrahamScan(long n){
SetMinimum(n);
total=n;
AngleSort(n);
h[0][0]=p[0][0];
h[0][1]=p[0][1];
h[1][0]=p[1][0];
h[1][1]=p[1][1];
h[2][0]=p[2][0];
h[2][1]=p[2][1];
long head=2,i;
for(i=3;i<total;i++)
{
while( Area(h[head-1][0],h[head-1][1],h[head][0],h[head][1],p[i][0],p[i][1])<=0)
{
head--;
}
head++;
h[head][0]=p[i][0];
h[head][1]=p[i][1];
}
return head+1;
}
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][0],&p[i][1]);
a[i]=1;
}
total =GrahamScan(n);
area=0.;
for(i=1;i<total-1;i++)
{
area+=.5 * fabs(Area(h[0][0],h[0][1],h[i][0],h[i][1],h[i+1][0],h[i+1][1]));
}
cx=0.;
cy=0.;
h[total][0]=h[0][0];
h[total][1]=h[0][1];
for(i=0;i<total;i++){
cx+= (h[i][0] +h[i+1][0])*(h[i][0] * h[i+1][1] -h[i+1][0] * h[i][1]);
cy+= (h[i][1] +h[i+1][1])*(h[i][0] * h[i+1][1] -h[i+1][0] * h[i][1]);
}
cx/=(6*area);
cy/=(6*area);
printf("%.3lf %.3lf\n",cx+1e-9,cy+1e-9);
}
}
..........................................................................................................
#include <stdio.h>
#include <math.h>
#define M_PI acos(-1.0)
long p[120][2],top[120],h[120][2],p2[120][2];
bool a[120];
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[0]-p[j][0])*(p[0]-p[j][0]) +
(p[1]-p[j][1])*(p[1]-p[j][1]));
}
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[0][0],p[0][1],p[0],p[1] ) > ang(p[0][0],p[0][1],p[j][0],p[j][1] ) )
{
Swap(p[0],p[j][0]);
Swap(p[1],p[j][1]);
}
}
}//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[0][0],p[0][1],p[0],p[i][1] ) ;
s= ang(p[0][0],p[0][1],p[j][0],p[j][1]) ;
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][0]=p[i][0];
p2[i][1]=p[i][1];
}
j=0;
for(i=0; i<n ; i++)
{
if(a[i]==1)
{
p[j][0]=p2[i][0];
p[j][1]=p2[i][1];
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][1] > p[index][1] ) continue;
else if( p[i][1] < p[index][1] )
index = i;
else{
if( p[i][0] < p[index][0] )
index = i;
}
}
Swap(p[0][0],p[index][0]);
Swap(p[0][1],p[index][1]);
}
long GrahamScan(long n){
SetMinimum(n);
total=n;
AngleSort(n);
h[0][0]=p[0][0];
h[0][1]=p[0][1];
h[1][0]=p[1][0];
h[1][1]=p[1][1];
h[2][0]=p[2][0];
h[2][1]=p[2][1];
long head=2,i;
for(i=3;i<total;i++)
{
while( Area(h[head-1][0],h[head-1][1],h[head][0],h[head][1],p[i][0],p[i][1])<=0)
{
head--;
}
head++;
h[head][0]=p[i][0];
h[head][1]=p[i][1];
}
return head+1;
}
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][0],&p[i][1]);
a[i]=1;
}
total =GrahamScan(n);
area=0.;
for(i=1;i<total-1;i++)
{
area+=.5 * fabs(Area(h[0][0],h[0][1],h[i][0],h[i][1],h[i+1][0],h[i+1][1]));
}
cx=0.;
cy=0.;
h[total][0]=h[0][0];
h[total][1]=h[0][1];
for(i=0;i<total;i++){
cx+= (h[i][0] +h[i+1][0])*(h[i][0] * h[i+1][1] -h[i+1][0] * h[i][1]);
cy+= (h[i][1] +h[i+1][1])*(h[i][0] * h[i+1][1] -h[i+1][0] * h[i][1]);
}
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
Try the following: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.
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
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
-
- New poster
- Posts: 19
- Joined: Wed Jan 11, 2006 9:57 am
- Location: Dhaka
Thanks ,for your reply Martin.
Thanks Martin for reply.
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.
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.
The following test case has
been posted a lot of time
ago on this thread.
My ACC program outputs:
Which is strange...
been posted a lot of time
ago on this thread.
Is this output correct?!Try this data
Input :
4
19999999999 1
1 3
3 1
1 2
1
Output :
6666666667.333 1.667
My ACC program outputs:
Code: Select all
6666652284.322 1.667
-
- 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
my profile
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?