## 10180 - Rope Crisis in Ropeland!

Moderator: Board moderators

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Hi !! I have a lot of WA!! in this one ... please help me here some I/O
which should be the output ??

Code: Select all

15
13 15 17 6 3
1 9 12 6 5
3 19 10 7 2
16 12 6 0 6
2 9 7 8 1
15 7 3 2 1
2 11 16 13 7
4 19 1 13 9
10 15 4 18 7
3 5 7 6 3
1 9 2 6 5
3 9 0 7 2
6 2 6 0 6
2 9 7 8 1
5 7 3 2 1
this one ??

Code: Select all

9.849
11.402
13.892
15.343
5.099
17.338
14.142
10.735
6.708
4.123
4.254
3.606
2.000
5.099
5.385
Keep posting

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Contact:
I am also gettin wa ..

my output for ur input is

Code: Select all

9.849
11.402
13.892
15.620
5.099
13.000
14.142
6.708
6.708
4.123
3.162
3.606
2.000
5.099
5.385
can anyone give accepted output for those input..

jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA
arif_pasha, my AC program gets the same results as you. I used doubles, and no epsilon by the way. Here are some more test cases.

Input:

Code: Select all

6
10.314 0 10.314 0 1.01
1.0 0 -1 0.0 1.0000
0 10000.00 0.0 -10000.0 10000
9999.9999885733332 0.0 -9999.9999885733332 0.0 9999.9999885733332
9999.9999885733333 0.0 -9999.9999885733333 0.0 9999.9999885733333
-10000.0 -10000.0 10000 10000 10000
-10.00074999 1.001 10.00074999 1.001 1.0001
-10.00074999 1.0 10.00074999 1.0 1.001
Output:

Code: Select all

0.000
3.142
31415.927
31415.926
31415.927
35707.963
20.001
20.002
I used scanf for reading input, so as far as I know, there could be extra spaces between numbers or numbers formatted as 1.0e02, etc.

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Contact:
i got the same output as u do. but still wa...

jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA

### try getting rid of your epsilon

Ok - arif_pasha, I looked at your code, and I think your epsilon is too big. Try getting rid of it. At the limit when the line is just touching the circle, both methods should give the same answer, so I don't think you need to use an epsilon in that case.

Here is a case that your code gives the wrong answer for (tailored to your epsilon of 1e-5), and another for an epsilon of 1e-7. I didn't try to defeat any smaller epsilon than that.:

Input:

Code: Select all

-0.012749999 9.999992 0.012749999 9.999992 10.0
-0.012749999 10 0.012749999 10 10.0
-0.001249999999 9.999999922 0.001249999999 9.999999922 10.0
-0.001249999999 10 0.001249999999 10 10.0
Output:

Code: Select all

0.026
0.025
0.003
0.002

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
Just got my code from WA for several days to AC. The last changes I made were as follows:
• Fix the code for checking that the two points are not the same.
Fix the code for checking the intersection between the intersection between the rope and the circle
Use double instead of long double
It's worthy (and weird) of note that I used an epsilon of 1e-5
Really hope this helps..this problem killed me for nearly a week

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
I am fade up with it !
my programme passed all the test cases here but its a series of WA i got from the judge! is there anyone to check my code plz ...

Code: Select all

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

#define PI 2*acos(0.0)
#define EPS 1e-5

class point
{
public:
long double x,y;
point()
{
}
point(long double a,long double b)
{
x=a;
y=b;
}
};

class line
{
public:
long double a;
long double b;
long double c;
line()
{
}
line(point p1,point p2)
{
a=p1.y-p2.y;
b=p2.x-p1.x;
c=p1.y*(p1.x-p2.x)-p1.x*(p1.y-p2.y);
}

};

long double dis_p2p(point p1,point p2) //function for determining distance between 2 points
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

long double dis_p2l(line L,point p)//function for determining distance between a line and a point
{
long double d=fabs(L.a*p.x+L.b*p.y+L.c);
d/=sqrt(L.a*L.a+L.b*L.b);
return d;
}

long double Angle(point p)
{
if(fabs(p.x-0.0)<EPS)
{
if(fabs(p.y-0.0)<EPS)
{
return 0;
}
if(p.y<0.0)
{
return PI+PI/2;
}
return PI/2;
}
if(p.y<0.0)
{
return atan(p.x/p.y)+ PI;
}
return atan(p.x/p.y);
}

int main(void)
{
int n;
point p1,p2;
point origin(0,0);
long double r;
scanf("%d",&n);
while(n--)
{
scanf("%Lf%Lf%Lf%Lf%Lf",&p1.x,&p1.y,&p2.x,&p2.y,&r);
line L(p1,p2);
if(dis_p2l(line(p1,p2),point(0.0,0.0))>=r || (p1.x*p2.x>=0.0 && p1.y*p2.y>=0.0))
{
printf("%.3Lf\n",dis_p2p(p1,p2));
}
else
{
long double d1=sqrt(dis_p2p(origin,p1)*dis_p2p(origin,p1)-r*r);
long double d2=sqrt(dis_p2p(origin,p2)*dis_p2p(origin,p2)-r*r);
long double a1=acos(r/dis_p2p(origin,p1));
long double a2=acos(r/dis_p2p(origin,p2));
long double A1=Angle(p1);
long double A2=Angle(p2);
long double a=fabs(A1-A2)-fabs(a1+a2);
long double d3=a*r;
printf("%.3Lf\n",d1+d2+d3);
}
}
return 0;
}
Syed Ishtiaque Ahmed Kallol
CSE,BUET

ferrizzi
New poster
Posts: 23
Joined: Thu Mar 30, 2006 5:42 pm
Location: Brazil

### WA

Hi!
Could someone give me some input/output for this problem?

Regards,
[]'s
Andre

ferrizzi
New poster
Posts: 23
Joined: Thu Mar 30, 2006 5:42 pm
Location: Brazil
I used the same approach and I got AC.
Regards,
[]'s
Andre

sabi
New poster
Posts: 1
Joined: Thu Aug 24, 2006 7:37 am
Contact:

### 10180

I got too many WA for the problem 10180 , but when i changed my
long double temp = acos(temp1) ;
to
long double temp = acos((temp1) <? 1 >? -1);
i get it Accepted

1 - use the epsilon 1e-7
2 - use long double
for example :
bool less(long double a,long double b)
{
return (a-b)<EPS;
}

Hope it Helps
Good Luck
What we do in life echoes in Eternity .

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the cases. Some of these were posted already but correct answers weren't posted.

Input:

Code: Select all

17
-5 0 5 -1 5
10 10 -10 -10 5
13 15 17 6 3
1 9 12 6 5
3 19 10 7 2
16 12 6 0 6
2 9 7 8 1
15 7 3 2 1
2 11 16 13 7
4 19 1 13 9
10 15 4 18 7
3 5 7 6 3
1 9 2 6 5
3 9 0 7 2
6 2 6 0 6
2 9 7 8 1
5 7 3 2 1
Output:

Code: Select all

14.734
30.071
9.849
11.402
13.892
15.620
5.099
13.000
14.142
6.708
6.708
4.123
3.162
3.606
2.000
5.099
5.385
Hope these help.
Ami ekhono shopno dekhi...
HomePage

iran
New poster
Posts: 6
Joined: Sat Feb 03, 2007 4:46 pm

### 10180 how many wrong

if somebody find why this code go wrong he or she is really clever!
it pass all testdata in past topics.
[img]
http://www.sharemation.com/taksavar7/ro ... niq=gu7lot
[/img]

Code: Select all

// In the name of God
// 10180
#include <iostream>
#include <cmath>

using namespace std;

#define pow2(a) ((a)*(a))

struct Point
{
double x, y;
};
//-----------------------------------------------------------------------------
int main ()
{
//freopen( "a.in", "r", stdin );
int N;
Point p1, p2;
double r, d1, d2, x1, x2, a1, a2;

cout.precision( 3 );
cout.setf( ios::fixed | ios::showpoint );

for( cin >> N; N--; )
{
cin >> p1.x >> p1.y >> p2.x >> p2.y >> r;
if( p1.x == p2.x && p1.y == p2.y )
{
cout << 0.0 << endl;
continue;
}

d1 = sqrt( pow2(p1.x) + pow2(p1.y) );//Distance( Point( 0, 0 ), p1 );
x1 = sqrt( pow2(d1) - pow2(r) );
a1 = acos( r/d1 );

d2 = sqrt( pow2(p2.x) + pow2(p2.y) ); //Distance( Point( 0, 0 ), p2 );
x2 = sqrt( pow2(d2) - pow2(r) );
a2 = acos( r/d2 );

double dot = p1.x * p2.x + p1.y * p2.y;
double angle = acos( dot / (d1 * d2 ) ), res;

angle = angle - ( a1 + a2 );

if( angle < 0 || abs( angle ) < 1e-5 ) // Distance between two point
res = sqrt( pow2(p1.x - p2.x) + pow2(p1.y - p2.y) );
else
res = x1 + x2 + ( angle * r );

cout << res << endl;
}
return 0;
}
Last edited by iran on Tue Aug 14, 2007 12:02 pm, edited 2 times in total.

New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran
I generate about 1000 testcase and compare your code with my AC code and two files are equal
I don't know why you got WA but I like your idea (using dot product) because it guarantee that always the arc length will be minimum. I think the judge input maybe wrong, I'm not sure.

mfs
New poster
Posts: 1
Joined: Wed Aug 29, 2007 2:30 pm

### i wana cry

i have this problem too
it seems to be correct but i get WA as same as you.

HELP please what's our mistake ????

Hojjat jafary
New poster
Posts: 10
Joined: Sun Sep 16, 2007 9:35 am
I think this method have precision error because of using the cos function but input should be compatible with output of all methods that are correct not only for the method of problemseter.