10180 - Rope Crisis in Ropeland!

[andysoft]

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

  readln (cn);

  for ci := 0 to cn - 1 do
  begin
    readln (x1,y1,x2,y2,r);

    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.

[sijal]

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.

[cyclops_kun]

Please Help..
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]

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++ */
//Técnicas Utilizadas: --
#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]

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]

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]

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]

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

[NAbdulla]

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]

Next time post in the existing thread.

Read this thread. Your code fails on some of the I/O posted.