## 10180 - Rope Crisis in Ropeland!

Moderator: Board moderators

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Sorry for disturbing everyone here, but I simply don't know what to do. I try everything and get ok outs for all inputs here...

Code: Select all

``````program Project3;

{\$APPTYPE CONSOLE}

uses
SysUtils, Math;

const
eps = 1e-5;

function distance (const x1,y1,x2,y2: extended): extended;
var
a,b,t: extended;
begin
a := sqr (x1-x2);
b := sqr (y1-y2);
t := a + b;
t := sqrt (t);
distance := t
end;

function distanceToLineSegment (const x,y,x1,y1,x2,y2: extended): extended;
var
a,b,c,t: extended;
aa,bb,cc: extended;
begin
a := y2 - y1;
b := x1 - x2;
c := -abs(-x1*a - y1*b);
t := sqrt (sqr(a)+sqr(b));

if abs(a*x + b*y +c)<eps then
begin
if (x>=min(x1,x2)-eps) and (x<=max(x1,x2)+eps) and (y>=min(y1,y2)-eps) and (y<=max(y1,y2)+eps) then
distanceToLineSegment := 0
else
distanceToLineSegment := maxint
end
else
begin
aa := sqr(distance (x,y,x1,y1));
bb := sqr(distance (x,y,x2,y2));
cc := sqr(distance (x1,y1,x2,y2));
if (aa>bb+cc) or (bb>aa+cc) then
distanceToLineSegment := min (aa,bb)
else
distanceToLineSegment := abs( (a*x + b*y + c)/t )
end;
end;

var
x1,y1,x2,y2,r: extended;
a,b,c: extended;
d: extended;
d1,d2: extended;
ci,cn: integer;
ax1,ay1,ax2,ay2: extended;
alpha,beta1,beta2,beta: extended;
x11,y11,x12,y12,x21,y21,x22,y22: extended;
a1,a2,a3,a4: extended;
di: extended;

begin

for ci := 0 to cn - 1 do
begin

if (x1=x2) and (y1=y2) then
begin
writeln (0.0:0:3);
continue
end;

{ transform (x1,y1);
transform (x2,y2);}

d := distanceToLineSegment (0,0,x1,y1,x2,y2);

if d>r-eps then
begin
writeln (distance(x1,y1,x2,y2):0:3);
continue
end;

d := sqrt (sqr(x1) + sqr(y1));
alpha := arcsin (r/d);
alpha := pi/2.0 - alpha;

beta := arctan2 (y1,x1);
while beta<0 do
beta := beta + 2*pi;
beta1 := beta + alpha;
beta2 := beta - alpha;

{    if abs(beta1)<eps then
beta1 := 0;
if abs(beta2)<eps then
beta2 := 0;    }

x11 := r*cos (beta1);
y11 := r*sin (beta1);
x12 := r*cos (beta2);
y12 := r*sin (beta2);

d := sqrt (sqr(x2) + sqr(y2));
alpha := arcsin (r/d);
alpha := pi/2.0 - alpha;

beta := arctan2 (y2,x2);
beta1 := beta + alpha;
beta2 := beta - alpha;

x21 := r*cos (beta1);
y21 := r*sin (beta1);
x22 := r*cos (beta2);
y22 := r*sin (beta2);

a1 := arctan2 (y11,x11);
a2 := arctan2 (y12,x12);
a3 := arctan2 (y21,x21);
a4 := arctan2 (y22,x22);

alpha := min ( min(abs(a1-a3),abs(a1-a4)) , min(abs(a2-a3),abs(a2-a4)) );

d1 := alpha*r;

d2 :=      min (distance (x1,y1,x11,y11), distance (x1,y1,x12,y12));
d2 := d2 + min (distance (x2,y2,x21,y21), distance (x2,y2,x22,y22));
d := d1 + d2;

writeln (d:0:3)

end;

end.
``````
Now I lay me down to sleep...
my profile

sijal
New poster
Posts: 9
Joined: Fri Jul 18, 2008 12:10 pm
Location: Iran-shiraz
Contact:

### Re: 10180 - Rope Crisis in Ropeland !

i love this problem , i got AC in first try . my program didnt work for some inputs with high precision in this thread , you dont need such precion. i use e-7 as epsilon.
Learn to swim.

cyclops_kun
New poster
Posts: 4
Joined: Mon Dec 08, 2008 11:03 am

### I got AC in UVa judge, but i got WA in Programming-challenge

I got AC in UVa judge, but why i got WA in http://www.programming-challenges.com judge? I don't understand..
I'm sorry posting my AC code here , but, for me it's still WA , coz it's WA in programming-challenges, please help..thanks in advance..

Here is my code, for anyone who got AC, please try at http://www.programming-challenges.com and please tell me why i got WA there?

Code: Select all

``````#include<iostream>
#include<cmath>
#include<iomanip>

using namespace std;

double panjang(double x1, double y1, double x2, double y2);
double sudut(double a, double c);
void DistanceFromLine(double ax, double ay , double bx, double by );

double distanceLine, distanceSegment;

int main()
{
double x1, y1, x2, y2, r, L1, L2, L3, A, B, C, c, busur, hasil;
int N, i;

cin>>N;
for(i=0; i<N; i++)
{
cout<<fixed<<showpoint<<setprecision(3);
cin>>x1>>y1>>x2>>y2>>r;
L1=panjang(x1, y1, 0, 0);
L2=panjang(x2, y2, 0, 0);
L3=panjang(x1, y1, x2, y2);

DistanceFromLine(x1,y1,x2,y2);
if(distanceSegment>=r || L3==0)
hasil=L3;
else
{
A=sudut(r, L1);
B=sudut(r, L2);
C=acos((L3*L3-L2*L2-L1*L1)/(-2*L2*L1));
c=C-A-B;
busur=c*r;
hasil=busur+sqrt(L1*L1-r*r)+sqrt(L2*L2-r*r);
}
cout<<hasil<<endl;
}
return 0;
}

double panjang(double x1, double y1, double x2, double y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

double sudut(double a, double c)
{
return acos(a/c);
}

void DistanceFromLine(double ax, double ay ,  double bx, double by)
{
int cx=0;
int cy=0;
double r_numerator = (cx-ax)*(bx-ax) + (cy-ay)*(by-ay);
double r_denomenator = (bx-ax)*(bx-ax) + (by-ay)*(by-ay);
double r = r_numerator / r_denomenator;

double px = ax + r*(bx-ax);
double py = ay + r*(by-ay);

double s =  ((ay-cy)*(bx-ax)-(ax-cx)*(by-ay) ) / r_denomenator;

distanceLine = fabs(s)*sqrt(r_denomenator);

double xx = px;
double yy = py;

if ( (r >= 0) && (r <= 1) )
{
distanceSegment = distanceLine;
}
else
{

double dist1 = (cx-ax)*(cx-ax) + (cy-ay)*(cy-ay);
double dist2 = (cx-bx)*(cx-bx) + (cy-by)*(cy-by);
if (dist1 < dist2)
{
xx = ax;
yy = ay;
distanceSegment = sqrt(dist1);
}
else
{
xx = bx;
yy = by;
distanceSegment = sqrt(dist2);
}

}

}

``````

diego_engcomp
New poster
Posts: 9
Joined: Sat Jul 18, 2009 1:18 am

### Re: 10180 - Rope Crisis in Ropeland !

My problem is the opposite of the guy above. I got AC at programming challenges and WA at UVA. My program works for all test cases on this topic except one (only one of the test cases posted by jdmetz), in which my program prints 1#IO (I think it is Not a Number - NaN). Therefore, I think that the problem is overflow. I appreciate any help. Sorry for my english.

Code: Select all

``````//Rope Crisis in Ropeland!
/* @JUDGE_ID: 00000 10180 C++ */
#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;

#define PI 3.141592653589793
#define _inline(f...) f() __attribute__((always_inline)); f
const double EPS = 1e-7;

_inline(int cmp)(double x, double y = 0, double tol = EPS) {
return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
}

struct point{
double x,y;
point(double x=0.0, double y=0.0):x(x), y(y){}
};

struct line{
double a;
double b;
double c;
};

double dist(point p1, point p2){
return sqrt(pow(p2.x-p1.x,2.0)+pow(p2.y-p1.y,2.0));
}

void points_to_line(point p1, point p2, line *l){
if (p1.x==p2.x) {
l->a=1.0;
l->b=0.0;
l->c=-p1.x;
}else{
l->b=1.0;
l->a=-(p1.y-p2.y)/(p1.x-p2.x);
l->c=-(l->a*p1.x)-(l->b*p1.y);
}
}

void point_and_slope_to_line(point p, double m, line *l){
l->a=-m;
l->b=1.0;
l->c=-((l->a*p.x)+(l->b*p.y));
}

void intersection_point(line l1, line l2, point *p){
p->x=(l2.b*l1.c-l1.b*l2.c)/(l2.a*l1.b-l1.a*l2.b);
if (fabs(l1.b)>EPS) /* test for vertical line */
p->y=-(l1.a*(p->x)+l1.c)/l1.b;
else
p->y=-(l2.a*(p->x)+l2.c)/l2.b;
}

void closest_point(point p_in, line l, point *p_c){
line perp; /* perpendicular to l through (x,y) */
if (fabs(l.b)<=EPS) { /* vertical line */
p_c->x=-(l.c);
p_c->y=p_in.y;
return;
}
if (fabs(l.a)<=EPS) { /* horizontal line */
p_c->x=p_in.x;
p_c->y=-(l.c);
return;
}
point_and_slope_to_line(p_in,1.0/l.a,&perp); /* normal case */
intersection_point(l,perp,p_c);
}

bool point_in_box(point p1, point p2, point pt){
double min_x=min(p1.x,p2.x);
double max_x=max(p1.x,p2.x);
double min_y=min(p1.y,p2.y);
double max_y=max(p1.y,p2.y);
if(cmp(pt.x,min_x)>=0 && cmp(pt.x,max_x)<=0 && cmp(pt.y,min_y)>=0 && cmp(pt.y,max_y)<=0)
return true;
return false;
}

bool isPerpendicular(point p, point t){
line l1, l2;
points_to_line(p,t,&l1);
points_to_line(point(0.0,0.0),t,&l2);
if (cmp(l1.a,0.0)==0)
return(cmp(l2.b,0.0)==0);
else if (cmp(l2.a,0.0)==0)
return(cmp(l1.b,0.0)==0);
else
return (cmp(l1.a,(-1.0/l2.a))==0);
}

void tangentPoints(point p, double r, point &t1, point &t2){
if(cmp(r*r-p.x*p.x-p.y*p.y,0.0)==0){
t1=point(p.x,p.y);
t2=point(p.x,p.y);
return;
}
double a=(p.x*p.x+p.y*p.y);
double b=-2.0*r*r*p.x;
double c=r*r*r*r-p.y*p.y*r*r;
double delta=b*b-4*a*c;
double s1=(-b+sqrt(delta))/(2.0*a);
double s2=(-b-sqrt(delta))/(2.0*a);
t1=point(s1,sqrt(r*r-s1*s1));
if (!isPerpendicular(p,t1))
t1.y*=-1.0;
t2=point(s2,sqrt(r*r-s2*s2));
if (!isPerpendicular(p,t2))
t2.y*=-1.0;
}

double getArch(point p1, point p2, double r){
double a=dist(p1,p2);
double teta=acos((pow(a,2.0)-pow(r,2.0)-pow(r,2.0))/(-2.0*r*r));
return (r*teta);
}

int main(){
int n;
point p1, p2, pc, t1_p1, t2_p1, t1_p2, t2_p2;
double r,arch1,arch2,min_arch;
line l;
cin>>n;
for(int i=0; i<n; i++){
cin>>p1.x>>p1.y>>p2.x>>p2.y>>r;
if(cmp(dist(p1,p2),0.0)==0){
cout<<"0.000\n";
continue;
}
points_to_line(p1,p2,&l);
closest_point(point(0.0,0.0), l, &pc);
if(cmp(dist(point(0.0,0.0),pc),r)<0 && point_in_box(p1,p2,pc)){
tangentPoints(p1,r,t1_p1,t2_p1);
tangentPoints(p2,r,t1_p2,t2_p2);
if(cmp(dist(t1_p1,t1_p2),dist(t1_p1,t2_p2))<=0)
arch1=getArch(t1_p1,t1_p2,r);
else
arch1=getArch(t1_p1,t2_p2,r);
if(cmp(dist(t2_p1,t1_p2),dist(t2_p1,t2_p2))<=0)
arch2=getArch(t2_p1,t1_p2,r);
else
arch2=getArch(t2_p1,t2_p2,r);
min_arch=min(arch1,arch2);
printf("%4.3f\n",dist(p1,t1_p1)+min_arch+dist(p2,t1_p2));
}else
printf("%4.3f\n",dist(p1,p2));
}
return 0;
}

``````

cjtoribio
New poster
Posts: 1
Joined: Wed Apr 20, 2011 10:09 pm

### Re: 10180 - Rope Crisis in Ropeland !

My code solves every case in this forum and i have epsilon 1e-9 i dont know whats wrong please post more testcases

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long Long;
struct Pt
{
double x,y;
Pt(double a,double b)
{
x = a; y = b;
}
double operator *(const Pt &P)const
{
return x*P.x + y*P.y;
}
Pt operator -(const Pt &P)const
{
return Pt(x-P.x, y-P.y);
}
};
typedef Pt Point;
double sdist(Point A, Point B)
{
return (A-B)*(A-B);
}

double length(Point A,Point B,double R)
{
Point C(0,0);
double dAC = A.x*A.x + A.y*A.y;
double dBC = B.x*B.x + B.y*B.y;
double dAB = sdist(A,B);
if(R < 1e9)return sqrt(dAB);
double angl = acos((dBC+dAC-dAB)/(2.0*sqrt(dAC)*sqrt(dBC)));
double T1 = acos(R/sqrt(dAC));
double T2 = acos(R/sqrt(dBC));
angl -= T1 + T2;
if(angl < 1e-9)return sqrt(dAB);
if(dAC - R*R < 0 && dBC - R*R < 0)return angl*R;
if(dAC - R*R < 0)return sqrt(dBC - R*R) + angl*R;
if(dBC - R*R < 0)return sqrt(dAC - R*R) + angl*R;
return sqrt(dAC - R*R) + sqrt(dBC - R*R) + angl*R;
}

int main(int argc, char** argv)
{
int TC;
freopen("in.txt","r",stdin);
cin>>TC;
for(int tc = 1; tc<=TC; ++tc)
{
double X1,Y1,X2,Y2,R;
scanf("%lf %lf %lf %lf %lf",&X1,&Y1,&X2,&Y2,&R);
printf("%0.3lf\n",length(Point(X1,Y1),Point(X2,Y2),R));
}
return 0;
}

/*
* File:   10180.cpp
* Author: Soporte Tecnico
*
* Created on 20 de abril de 2011, 07:00 AM
*/
``````

eric7237cire
New poster
Posts: 4
Joined: Sat Mar 30, 2013 4:06 pm

### Re: 10180 - Rope Crisis in Ropeland !

I am pretty sure they have cases like

10.05 10.05 10.05 10.05 3

which in my case made a function return Nan which throws off comparisons. ie

5 < nan is false but 5 >= nan is also false.

Anyway, make sure you handle the case when the x1,y1 and x2, y2 are the exact same.

Happyfly
New poster
Posts: 2
Joined: Wed May 14, 2014 3:57 pm

### Re: 10180 - Rope Crisis in Ropeland !

I hvae got following info

double ang = acos((ab * ab + ac * ac - bc * bc) / (2.0 * ab * ac)); //AC

double ang = acos(a*b / (a.norm()*b.norm())); //WA

ab,ac,bc are the side of the triangle
a.norm() is the distance between a and orgin (0,0)

Have somebody know why using dot product to calc the angle gets wrong answer....

Appreciate a lot!

Happyfly
New poster
Posts: 2
Joined: Wed May 14, 2014 3:57 pm

### Re: 10180 - Rope Crisis in Ropeland !

Finally , I get it caused by the precision.It may help you.

NAbdulla
New poster
Posts: 31
Joined: Wed Jul 30, 2014 3:40 pm
Contact:

### 10180 - Rope Crisis in Ropeland! WA

What's wrong:
thinking:
code:

Code: Select all

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

int ch(double a, double b)
{
if((a > 0 && b < 0) || (a < 0 && b > 0))return 1;
else return 2;
}

int main()
{
int t;
double x1, y1, x2, y2, r, d, d1, d2, t1, t2, pl, m, rl, theta, arc;
scanf("%d", &t);
while(t--){
scanf("%lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &r);
if(x1 == x2){
if(fabs(x1) <= r && fabs(y1) >= r && fabs(y2) >= r && ch(y1, y2) == 2)pl = fabs(y1);
else pl = fabs(x1);
}
else if(y1 == y2){
if(fabs(y1) <= r && fabs(x1) >= r && fabs(x2) >= r && ch(x1, x2) == 2)pl = fabs(x1);
else pl = fabs(y1);
}
else{
m = (y2 - y1) / (x2 - x1);
pl = fabs((- m*x1 + y1) / sqrt(pow(m, 2) + 1));
}
if(pl >= r)rl = sqrt(pow((x1-x2), 2) + pow((y1-y2), 2));
else{
t1 = sqrt(pow(x1, 2) + pow(y1, 2) - pow(r, 2));
t2 = sqrt(pow(x2, 2) + pow(y2, 2) - pow(r, 2));
d1 = sqrt(pow(x1, 2) + pow(y1, 2));
d2 = sqrt(pow(x2, 2) + pow(y2, 2));
d = sqrt(pow((x1-x2), 2) + pow((y1-y2), 2));
theta = (acos((pow(d1, 2) + pow(d2, 2) - pow(d, 2)) / (2*d1*d2))) - ((acos((pow(d1, 2) + pow(r, 2) - pow(t1, 2)) / (2*d1*r))) + (acos((pow(d2, 2) + pow(r, 2) - pow(t2, 2)) / (2*r*d2))));
arc = theta * r;
rl = t1 + arc + t2;
}
printf("%.3lf\n", rl);
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10180 - Rope Crisis in Ropeland!

Next time post in the existing thread.