OJ Board

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

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

Thanks in advance !!
Keep posting

Posted: **Thu Mar 10, 2005 7:01 pm**

I am also gettin wa ..

my output for ur input is

Code: Select all

can anyone give accepted output for those input..

Posted: **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

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.

Posted: **Mon Jul 11, 2005 7:25 pm**

i got the same output as u do. but still wa...

Posted: **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

Posted: **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

Really hope this helps..this problem killed me for nearly a week

Posted: **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;
}

Posted: **Thu Aug 31, 2006 4:27 pm**

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

Thanks in advance!

Posted: **Thu Aug 31, 2006 10:11 pm**

I used the same approach and I got AC.

Posted: **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

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

Posted: **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

Hope these help.

Posted: **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;
}

Posted: **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

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.

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

Posted: **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.

OJ Board

10180 - Rope Crisis in Ropeland!

try getting rid of your epsilon

WA

10180

10180 how many wrong

i wana cry