10180 - Rope Crisis in Ropeland!

[Sujoy Kumar Chowdhury]

Would anyone be kind enough to provide some CRITICAL sample input output for 10180 ?

Is the following partial_algorithm correct?

case: the circle is in between the two points p1 and p2
distance = distance(p1, t1) + arclength(t1, t2) + distance( t2, p2)

/*where t1 is the contact point of the tangent from p1
and t2 is the contact point of the tangent from p2
and t1 and t2 taken such that arclength(t1, t2) is minimum*/

Thanks in advance.

[BiK]

I also tried the same algorithm and got WA. javascript:emoticon(':(')

Do you think the problem is with rounding errors?

I also tried some round-arithmetic ( for example, I assume a equals b, if abs(a-b)<EPSILON ) with EPSILON=0.000001 and I still get WA.

The success-rate of this problem is also very low... I am very curious where the problem is?

[little joey]

[EDIT] forget it, I made a stupid mistake...

[Observer]

I hate this problem.

I got loads of WA, but after taking EPS = 1E-5 and using extended (i.e. long double) instead of double, I get Accepted at once! Stupid rounding problem......

To make this task "more solvable", I have two suggestions for the system admins:
1. Use only integers in the input;
2. Add a special judge that allows small errors.
These won't make the problem easier, but the acceptance rate can be improved.

btw, the above partial algorithm is correct.

Finally, some simple test cases:

Code: Select all

10
-10 5 10 5 2
0 5 0 10 4
0 5 0 10 5
0 5 8 5 5
-8 5 8 5 5
9 9 9 9 2
0 1 -1 -1 1
0 1 0 -1 1
1 1 -1 -1 1
0 2 0 -2 1

And the output should be:

Code: Select all

20.000
5.000
5.000
8.000
16.000
0.000
2.571
3.142
3.571
4.511

Good luck!

[fpmc]

Observer, thank you for your test cases. I got accepted on second try after reading it.

However, I don't think the test cases were that sensitive. I used double, and my code don't even have an epsilon. I don't think I needed to use epsilons as the boundary cases for the two different formulae should yield very close answers as long as the formulae are not sensitive to round-off errors.

To lessen round-off errors, I first rotated the two vertices so that the first vertex is on the negative x-axis, and used determinants to determine whether the two points intersect the circle with a straight line. No division here so very minimal chances for errors.

Hope this helps,

Frank

[Observer]

Congrats~ You've proved that my algorithm can be much improved

What I write above is just some advices to Pascal programmers who are struggling hard with this problem. Maybe that could help somebody. Who knows?

[Renato]

I have a huge code for this problem, but I'm still getting WA I have tested my code with all i/o I could find. So, how can I determine if the output is the distance between the two points? I think my mystake is in this part... I'm doing this:

And... what is the equation to find the points of tangency? I found it like this:

Code: Select all

	double A = ((r.b*r.b) + (r.a*r.a))/(r.a*r.a);
 	double B = (-2*r.b*r.c) + ((2*c.centro.x*r.b)/r.a) + (2*c.centro.y);
	double C = ((2*c.centro.x*r.c)/r.a) + (c.centro.x*c.centro.x) + (c.centro.y*c.centro.y) - (c.r*c.r);
	double Y1 = ((-1*B) + sqrt((B*B) - (4*A*C)))/(2*A);
	double Y2 = ((-1*B) - sqrt((B*B) - (4*A*C)))/(2*A);
	double X1 = (-1*r.b*Y1 - r.c)/r.a;
	double X2 = (-1*r.b*Y2 - r.c)/r.a;

Is it correct? If anyone can give some I/O will be great!

Thanks in advice!

[Renato]

I have a huge code for this problem, but I'm still getting WA I have tested my code with all i/o I could find. So, how can I determine if the output is the distance between the two points? I think my mystake is in this part... I'm doing this:

And... what is the equation to find the points of tangency? I found it like this:

Code: Select all

   double A = ((r.b*r.b) + (r.a*r.a))/(r.a*r.a); 
    double B = (-2*r.b*r.c) + ((2*c.centro.x*r.b)/r.a) + (2*c.centro.y); 
   double C = ((2*c.centro.x*r.c)/r.a) + (c.centro.x*c.centro.x) + (c.centro.y*c.centro.y) - (c.r*c.r); 
   double Y1 = ((-1*B) + sqrt((B*B) - (4*A*C)))/(2*A); 
   double Y2 = ((-1*B) - sqrt((B*B) - (4*A*C)))/(2*A); 
   double X1 = (-1*r.b*Y1 - r.c)/r.a; 
   double X2 = (-1*r.b*Y2 - r.c)/r.a; 

where r is the line (ax + by + c = 0) and c is the circle. c.centro means the central point and c.r the circle radius.

Is it correct? If anyone can give some I/O will be great!

Thanks in advice!

[Renato]

It was precision problem...

[Renato]

It was precision problem, now I got AC

[Antonio Ocampo]

Please, help me I got WA several times.

Code: Select all

#include <cstdio>
#include <cmath>

using namespace std;

void main()
{
      int casos;
      double x1,x2,y1,y2,r,A,B,C,drecta,d1,d2,a1,a2,l1,l2,a,pimedios=acos(0.0);

      scanf("%i",&casos);

      do
      {
         scanf("%lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&r);

         A=y2-y1;   //coeficientes de la ec de la recta q une ambos puntos
         B=x1-x2;
         C=y1*x2-x1*y2;

         if(C<0.0)
          C=-C;

         drecta=sqrt(A*A+B*B);

         if(  C  > r*drecta )  // No toca a la circunferencia
          printf("%.3lf\n",drecta);

         else   //toca a la circunferencia
         {
            d1=sqrt(x1*x1+y1*y1);
            d2=sqrt(x2*x2+y2*y2);
            l1=sqrt(d1*d1-r*r);
            a1=acos(r/d1);

            if(a1>=pimedios)
             a1-=pimedios;

            l2=sqrt(d2*d2-r*r);
            a2=acos(r/d2);

            if(a2>pimedios)
             a2-=pimedios;

            a=acos( 0.5*(d1*d1+d2*d2-drecta*drecta)/(d1*d2) );

            printf("%.3lf\n",l1+l2+(a-a1-a2)*r);
         }
      }
      while(--casos);
}

Thanks in advance.

[PerHagen]

hello antonio my code is
#include <stdio.h>
#include <iostream.h>
#include <math.h>

void main (void){
int ntest,i;long double l1,l2,x1,x2,y1,y2,p,R,length;long double d10,d12,d20,h;
scanf("%d",&ntest);
for (i=1;i<=ntest;i++){
scanf("%lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&R);
d12=sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
d10=sqrt( (x1)*(x1) + (y1)*(y1) );
d20=sqrt( (x2)*(x2) + (y2)*(y2) );

if ( (( d10+d20-d12)>0.00001) && ((d10+d12-d20)>0.00001) && ((d12+d20-d10)>0.00001)){
p=(d20+d12+d10)/2.0;
h=(2.0/d12)* sqrt( (p-d10)*(p-d12)*(p-d20)*p ) ; }
else h=0.0;

if ( (R-h)>=0.00001 && (h>=0.00001)){

length=(acos( ( (d10*d10) + (d20*d20) - (d12*d12) ) /(2*d10*d20) )
-acos( R/d10 ) - acos( R/d20 ) )*R ;
if (R/d10 != 1.0) l1=sqrt( d10*d10 - R*R );
else l1=0.0;
if (R/d20 != 1.0) l2=sqrt( d20*d20 - R*R);
else l2=0.0;
length+=l1+l2;
}

if( (h-R)>0.00001 )length=d12;
if (h==0.0)
if (d12<(d10+d20))length=d12;

printf("%.3lf\n",length);
}
}

danger with 0.00001 ,stupid error ,but my code is wrong answer!

[PerHagen]

help me ... any help ...this problem isn

[PerHagen]

i 'am going a crazy !!
help me

[arif_pasha]

I am tired of gettin wa in this problem . can anyone help me?

my algo::
1. compute distance of the segment [formed be the two points{p,q}] from the center.
2. if distance>= radius, then rope needed = distance(p,q)
3. else
x = length of tangent frm p
y = length of tangent frm q
s = min arclength between two points [ points are the intersections of circle with the tangents]

rope = x+y+s

here is my code::

Code: Select all

/**
@	ROPE CRISIS IN ROPELAND
@   ACM :: 10180
@	Arif Pasha
*/


#include <stdio.h>
#include <math.h>


#define min(a,b) (a)<(b)?(a):(b)

typedef double data;

const data pi = acos(-1.0);
const data epsilon = 1e-5;

class point
{
public:
	data x,y;
};

point p,q,c;
data r;

class Line
{
public:
	data a,b,c;

	Line(point p,point q)
	{
		a = q.y - p.y;
		b = p.x - q.x;
		c = q.x*p.y - p.x*q.y;
	}
	
};


data distance(point a,point b)
{
	data xx = a.x-b.x;
	data yy = a.y-b.y;

	return sqrt(xx*xx+yy*yy);
}


data pointSegDis(point s,point e,point p)
{
	
	data u;
	data dist,d1,d2;

	data LineMag = distance(s,e);
	
	u = ( ( ( p.x - s.x ) * ( e.x - s.x ) ) +
		( ( p.y - s.y ) * ( e.y - s.y ) ) ) /
		( LineMag * LineMag ) ;

	if( u<0.0 || u>1.0)
	{
		d1 = distance(p,e);
		d2 = distance(p,s);

		return min(d1,d2);
	}


	Line A = Line(s,e);

	dist = fabs( (A.a*p.x+A.b*p.y+A.c)/sqrt(A.a*A.a+A.b*A.b) );

	return dist;
}


int main()
{
	
	int n;

	data d1,d2,d,dist;
	data x,y,s,rope;
	data th1,th2,th,alpha;

	c.x = c.y = 0;

	scanf("%d",&n);

	while(n--)
	{
		
		scanf("%lf %lf %lf %lf %lf",&p.x,&p.y,&q.x,&q.y,&r);
		
		dist = pointSegDis(p,q,c);

		d = distance(p,q);

		if(dist>=r)
		{		
			rope = d;
		}
		else
		{
		
			d1 = distance(p,c);
			d2 = distance(q,c); 

			x = sqrt(d1*d1 - r*r);
			y = sqrt(d2*d2 - r*r);


			th1 = acos(r/d1);
			
			th2 = acos(r/d2);
			
			th = acos((d1*d1+d2*d2-d*d)/(2*d1*d2));

	
			alpha = th - th1 - th2;

			s = r*alpha;

			rope = x+ y + s; 			
			

		}

		printf("%.3lf\n",rope);


	}

return 0;
}