## 10180 - Rope Crisis in Ropeland!

Moderator: Board moderators

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

### 10180 - Rope Crisis in Ropeland!

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*/

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?

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
[EDIT] forget it, I made a stupid mistake...

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

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!

Renato Ferreira

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

### 10180

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!

Renato Ferreira

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

### ACCEPTED

It was precision problem...
Renato Ferreira

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

### ACCEPTED

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

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

### 10180

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

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

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima
i 'am going a crazy !!
help me
hello !

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

### 10180 [ Rope crisis in ropeland ]

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

``````