10002

yiuyuho · Post by **yiuyuho** » Mon Feb 07, 2005 9:03 pm

yes, thread. Thank You.

Antonio Ocampo · Post by **Antonio Ocampo** » Wed Feb 09, 2005 5:15 am

Hi fellows

I got WA with this output

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 · Post by **Yile** » Wed Mar 02, 2005 11:57 am

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;
}

sohel · Post by **sohel** » Wed Mar 02, 2005 2:28 pm

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.

Yile · Post by **Yile** » Wed Mar 02, 2005 3:37 pm

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 · Post by **Ndiyaa ndako** » Wed Oct 12, 2005 1:14 am

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 · Post by **UWeiss** » Tue Jan 31, 2006 11:26 pm

>> 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 · Post by **migichen** » Fri Mar 17, 2006 6:07 am

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

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 · Post by **CodeMaker** » Sat May 27, 2006 4:42 am

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

Shuvra(CSE-BUET) · Post by **Shuvra(CSE-BUET)** » Thu Aug 31, 2006 12:17 pm

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);

}

}

Martin Macko · Post by **Martin Macko** » Fri Sep 01, 2006 3:01 pm

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

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) · Post by **Shuvra(CSE-BUET)** » Fri Sep 01, 2006 3:14 pm

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.

Sedefcho · Post by **Sedefcho** » Sat Jun 02, 2007 2:44 pm

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

andysoft · Post by **andysoft** » Thu Jun 28, 2007 12:23 pm

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

Juanito · Post by **Juanito** » Fri Oct 31, 2008 10:01 am

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?

UVa OJ Board

10002 - Center of Masses

ooopsi daisy..

Convex hull

Ultima test data

i am getting WA for many times and I am hung

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

Thanks ,for your reply Martin.

Re: 10002 - Center of Masses