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

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Fri Nov 30, 2007 10:14 pm

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.
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 !

Post by sijal » Wed Sep 10, 2008 12:21 am

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

Post by cyclops_kun » Mon Dec 08, 2008 11:41 am

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 :cry: , 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 !

Post by diego_engcomp » Sat Dec 12, 2009 8:57 pm

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
New poster
Posts: 1
Joined: Wed Apr 20, 2011 10:09 pm

Re: 10180 - Rope Crisis in Ropeland !

Post by cjtoribio » Wed Apr 20, 2011 10:11 pm

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 !

Post by eric7237cire » Mon Apr 01, 2013 7:22 pm

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 !

Post by Happyfly » Wed May 14, 2014 4:07 pm

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! :D

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

Re: 10180 - Rope Crisis in Ropeland !

Post by Happyfly » Thu May 29, 2014 2:15 pm

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

Post by NAbdulla » Mon Oct 13, 2014 8:37 pm

What's wrong:
thinking: Image
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!

Post by brianfry713 » Mon Oct 13, 2014 11:23 pm

Next time post in the existing thread.

Read this thread. Your code fails on some of the I/O posted.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”