Page 4 of 4

Posted: Mon Feb 07, 2005 9:03 pm
by yiuyuho
yes, thread. Thank You.
:D

Posted: Wed Feb 09, 2005 5:15 am
by Antonio Ocampo
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 :wink:

10002

Posted: Wed Mar 02, 2005 11:57 am
by Yile

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..

Posted: Wed Mar 02, 2005 2:28 pm
by sohel
A part of your code.

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.

Posted: Wed Mar 02, 2005 3:37 pm
by Yile
Oh, thanks. If you don't tell me this, maybe I will never notice it. I fix it and get AC. Thank you again.

Convex hull

Posted: Wed Oct 12, 2005 1:14 am
by Ndiyaa ndako
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.

Posted: Tue Jan 31, 2006 11:26 pm
by UWeiss
>> 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...

Ultima test data

Posted: Fri Mar 17, 2006 6:07 am
by migichen
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 :lol:
See if u have the same prb. :wink:

Posted: Sat May 27, 2006 4:42 am
by CodeMaker
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 am getting WA for many times and I am hung

Posted: Thu Aug 31, 2006 12:17 pm
by Shuvra(CSE-BUET)
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);


}


}

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

Posted: Fri Sep 01, 2006 3:01 pm
by Martin Macko
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

Thanks ,for your reply Martin.

Posted: Fri Sep 01, 2006 3:14 pm
by Shuvra(CSE-BUET)
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.

Posted: Sat Jun 02, 2007 2:44 pm
by Sedefcho
The following test case has
been posted a lot of time
ago on this thread.
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...

Posted: Thu Jun 28, 2007 12:23 pm
by andysoft
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++.

Re: 10002 - Center of Masses

Posted: Fri Oct 31, 2008 10:01 am
by Juanito
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?