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.:
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
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 ...
#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;
}
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;
}
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.
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.
i got the same output as u do. but still wa...
