10180 - Rope Crisis in Ropeland!
Moderator: Board moderators
-
- New poster
- Posts: 2
- Joined: Mon May 05, 2003 2:14 am
- Location: Bangladesh
- 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*/
Thanks in advance.
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
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?
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?
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 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:](./images/smilies/icon_evil.gif)
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:And the output should be:
Good luck! ![:wink:](./images/smilies/icon_wink.gif)
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:](./images/smilies/icon_evil.gif)
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
Code: Select all
20.000
5.000
5.000
8.000
16.000
0.000
2.571
3.142
3.571
4.511
![:wink:](./images/smilies/icon_wink.gif)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
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
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
Congrats~ You've proved that my algorithm can be much improved ![:-)](./images/smilies/icon_smile.gif)
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](./images/smilies/icon_biggrin.gif)
![:-)](./images/smilies/icon_smile.gif)
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](./images/smilies/icon_biggrin.gif)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
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:
Is it correct? If anyone can give some I/O will be great!
Thanks in advice!
![:cry:](./images/smilies/icon_cry.gif)
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;
Thanks in advice!
Renato Ferreira
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:
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!
![:cry:](./images/smilies/icon_cry.gif)
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
-
- Experienced poster
- Posts: 131
- Joined: Sat Jul 17, 2004 4:09 am
- Location: Lima, Per
Please, help me I got WA several times.
Thanks in advance. ![:wink:](./images/smilies/icon_wink.gif)
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);
}
![:wink:](./images/smilies/icon_wink.gif)
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!
#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 !
-
- New poster
- Posts: 42
- Joined: Fri Jun 13, 2003 3:47 pm
- Location: Dhaka , Bangladesh
- 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::
![:(](./images/smilies/icon_frown.gif)
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;
}