Page 1 of 3

10180 - Rope Crisis in Ropeland!

Posted: Thu Sep 25, 2003 4:23 pm
by 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.

What is the problem with the Rope Crisis in Ropeland?

Posted: Wed Nov 12, 2003 4:56 pm
by 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?

Posted: Sat Jun 05, 2004 2:40 pm
by little joey
[EDIT] forget it, I made a stupid mistake...

Posted: Sun Jul 04, 2004 1:23 pm
by 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...... :evil:

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! :wink:

Posted: Sun Jul 18, 2004 3:10 pm
by 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

Posted: Sun Jul 18, 2004 5:11 pm
by 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? :D

WA

Posted: Thu Oct 07, 2004 5:05 am
by Renato
I have a huge code for this problem, but I'm still getting WA :cry: 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!

10180

Posted: Thu Oct 07, 2004 5:08 am
by Renato
I have a huge code for this problem, but I'm still getting WA :cry: 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!

ACCEPTED

Posted: Fri Oct 08, 2004 4:40 pm
by Renato
It was precision problem...

ACCEPTED

Posted: Fri Oct 08, 2004 4:41 pm
by Renato
It was precision problem, now I got AC

Posted: Sun Jan 30, 2005 6:04 am
by 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. :wink:

10180

Posted: Sun Feb 06, 2005 12:36 am
by 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!

hello

Posted: Tue Feb 08, 2005 12:57 am
by PerHagen
help me ... any help ...this problem isn

Posted: Tue Feb 08, 2005 1:04 am
by PerHagen
i 'am going a crazy !!
help me

10180 [ Rope crisis in ropeland ]

Posted: Sun Feb 27, 2005 12:21 am
by 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;
}