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

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
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 1e5), and another for an epsilon of 1e7. 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:

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 1e5
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
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 1e5
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.yp2.y;
b=p2.xp1.x;
c=p1.y*(p1.xp2.x)p1.x*(p1.yp2.y);
}
};
long double dis_p2p(point p1,point p2) //function for determining distance between 2 points
{
return sqrt((p1.xp2.x)*(p1.xp2.x)+(p1.yp2.y)*(p1.yp2.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.x0.0)<EPS)
{
if(fabs(p.y0.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(A1A2)fabs(a1+a2);
long double d3=a*r;
printf("%.3Lf\n",d1+d2+d3);
}
}
return 0;
}
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

ferrizzi
 New poster
 Posts: 23
 Joined: Thu Mar 30, 2006 5:42 pm
 Location: Brazil
Post
by ferrizzi » Thu Aug 31, 2006 4:27 pm
Hi!
Could someone give me some input/output for this problem?
Thanks in advance!
Regards,
[]'s
Andre

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:
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
some other advices :
1  use the epsilon 1e7
2  use long double
3  use your own less function instead of <
for example :
bool less(long double a,long double b)
{
return (ab)<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.

iran
 New poster
 Posts: 6
 Joined: Sat Feb 03, 2007 4:46 pm
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 ) < 1e5 ) // 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.

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

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.