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

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Wed Mar 09, 2005 4:28 pm

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
Thanks in advance !!
Keep posting

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Thu Mar 10, 2005 7:01 pm

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

Post by jdmetz » Mon Jul 11, 2005 4:21 pm

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
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Mon Jul 11, 2005 7:25 pm

:-? 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

Post by jdmetz » Tue Jul 12, 2005 7:03 pm

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

Post by mido » Tue Jul 12, 2005 9:49 pm

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 :roll:
Really hope this helps..this problem killed me for nearly a week :wink:

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Tue Aug 22, 2006 2:04 pm

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
Bangladesh

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

WA

Post by ferrizzi » Thu Aug 31, 2006 4:27 pm

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

Thanks in advance!
:D
Regards,
[]'s
Andre

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

Post by ferrizzi » Thu Aug 31, 2006 10:11 pm

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

Post by sabi » Mon Oct 23, 2006 10:32 pm

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

some other advices :
1 - use the epsilon 1e-7
2 - use long double
3 - use your own less function instead of <
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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Jun 13, 2007 11:40 pm

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

Post by iran » Mon Aug 13, 2007 8:47 am

if somebody find why this code go wrong he or she is really clever!
it pass all testdata in past topics.
link below show my approach.
[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.

User avatar
saman_saadi
New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran

Post by saman_saadi » Mon Aug 13, 2007 3:44 pm

I generate about 1000 testcase and compare your code with my AC code and two files are equal :o
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

Post by mfs » Mon Sep 03, 2007 9:13 pm

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

HELP please what's our mistake ???? :cry:

Hojjat jafary
New poster
Posts: 10
Joined: Sun Sep 16, 2007 9:35 am

Post by Hojjat jafary » Sun Sep 16, 2007 10:08 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.

Post Reply

Return to “Volume 101 (10100-10199)”