10180 - Rope Crisis in Ropeland!

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Sujoy Kumar Chowdhury
New poster
Posts: 2
Joined: Mon May 05, 2003 2:14 am
Location: Bangladesh
Contact:

10180 - Rope Crisis in Ropeland!

Post by Sujoy Kumar Chowdhury » Thu Sep 25, 2003 4:23 pm

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.
y%<U

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

What is the problem with the Rope Crisis in Ropeland?

Post by BiK » Wed Nov 12, 2003 4:56 pm

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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Jun 05, 2004 2:40 pm

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Jul 04, 2004 1:23 pm

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:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm

Post by fpmc » Sun Jul 18, 2004 3:10 pm

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Jul 18, 2004 5:11 pm

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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Renato
New poster
Posts: 5
Joined: Wed Oct 06, 2004 12:44 am
Location: Brazil
Contact:

WA

Post by Renato » Thu Oct 07, 2004 5:05 am

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!
Renato Ferreira

Renato
New poster
Posts: 5
Joined: Wed Oct 06, 2004 12:44 am
Location: Brazil
Contact:

10180

Post by Renato » Thu Oct 07, 2004 5:08 am

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!
Renato Ferreira

Renato
New poster
Posts: 5
Joined: Wed Oct 06, 2004 12:44 am
Location: Brazil
Contact:

ACCEPTED

Post by Renato » Fri Oct 08, 2004 4:40 pm

It was precision problem...
Renato Ferreira

Renato
New poster
Posts: 5
Joined: Wed Oct 06, 2004 12:44 am
Location: Brazil
Contact:

ACCEPTED

Post by Renato » Fri Oct 08, 2004 4:41 pm

It was precision problem, now I got AC
Renato Ferreira

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Jan 30, 2005 6:04 am

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:

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima

10180

Post by PerHagen » Sun Feb 06, 2005 12:36 am

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 !

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima

hello

Post by PerHagen » Tue Feb 08, 2005 12:57 am

help me ... any help ...this problem isn
hello !

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima

Post by PerHagen » Tue Feb 08, 2005 1:04 am

i 'am going a crazy !!
help me
hello !

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

10180 [ Rope crisis in ropeland ]

Post by arif_pasha » Sun Feb 27, 2005 12:21 am

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


Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest