## 10011 - Where Can You Hide?

Moderator: Board moderators

iamsleepy
New poster
Posts: 4
Joined: Thu Jul 27, 2006 7:50 am

### 10011 Where Can You Hide - WA

My solution to this problem is wa. I think it's a precision fault. Could someone give me an advice on it? THX...

Here is my code...

Code: Select all

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

inline long double absx(long double x){
return x-0>1.0e-8?x:-x;
}

char buffer[10];

int main(){
int v;
long double cx,cy,r,x0,y0;
double cxx,cyy,rr,xx0,yy0;
double k1,k2,dist;
int count=0;
scanf("%d",&v);
while(v--){
scanf("%lf%lf%lf%lf%lf",&cyy,&cxx,&rr,&yy0,&xx0);
cy=cyy;cx=cxx;r=rr;y0=yy0;x0=xx0;
strcpy(buffer,"");
if(cx<1.0e-8) {cx=-cx;x0=-x0;}
if(cy<1.0e-8) {cy=-cy;y0=-y0;}
if(absx(cx-r)<1.0e-8){
dist=cx;
cx=cy;
cy=dist;
dist=x0;
x0=y0;
y0=dist;
}
if(r<0||cx*cx+cy*cy<=r*r)
printf("0.000\n");
else{
if(absx(cx-r)<1.0e-8&&absx(cy-r)<1.0e-8){
if((x0<1.0e-8||y0<1.0e-8)||x0*x0+y0*y0-r*r<1.0e-8)//Tanglet with axis
printf("0.000\n");
else{
dist=sqrtl((x0-cx)*(x0-cx)+(y0-cy)*(y0-cy))-r;
if(dist>absx(x0)) dist=absx(x0);
if(dist>absx(y0)) dist=absx(y0);
if(dist-0<-1.0e-8)
printf("0.000\n");
else
printf("%.3lf\n",dist);

}
}
else{
/*k1=(-cx*cy-sqrt(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))/(r*r-cx*cx);
k2=(r*r-cy*cy)/(-cx*cy-sqrt(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)));*/
if((((-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))/(r*r-cx*cx)*x0-y0)*((-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))/(r*r-cx*cx)*cx-cy)<-1.0e-8||
((r*r-cy*cy)/(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))*x0-y0)*((r*r-cy*cy)/(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))*cx-cy)<-1.0e-8)||
cx*cx+cy*cy-r*r-x0*x0-y0*y0>1.0e-8)
printf("0.000\n");
else{
dist=sqrtl((x0-cx)*(x0-cx)+(y0-cy)*(y0-cy))-r;
if(dist-absx(y0-(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))/(r*r-cx*cx)*x0)/sqrtl(1+(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))/(r*r-cx*cx)*(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))/(r*r-cx*cx))>1.0e-8)
dist=absx(y0-(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))/(r*r-cx*cx)*x0)/sqrtl(1+(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))/(r*r-cx*cx)*(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))/(r*r-cx*cx));//Try to avoid rounding error...
if(dist-absx(y0-(r*r-cy*cy)/(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))*x0)/sqrtl(1+(r*r-cy*cy)/(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))*(r*r-cy*cy)/(-cx*cy-sqrt(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx))))>1.0e-8)
dist=absx(y0-(r*r-cy*cy)/(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))*x0)/sqrtl(1+(r*r-cy*cy)/(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx)))*(r*r-cy*cy)/(-cx*cy-sqrtl(cx*cx*cy*cy-(r*r-cy*cy)*(r*r-cx*cx))));
if(dist<-1.0e-8) printf("0.000\n");
else
printf("%.3lf\n",dist);
}
}
}
}
return 0;
}

Last edited by iamsleepy on Thu Aug 03, 2006 3:30 am, edited 5 times in total.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

iamsleepy
New poster
Posts: 4
Joined: Thu Jul 27, 2006 7:50 am
Please give me that data... I've tested all of them earlier than this submit and got the same answer as the poster.
P.S. At that time.. I was modifying my program, perhaps there may be some fault....

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

I see, you have passed all of those test cases. Let's see how I can help. Well I used only sqrt,long doubles, and have EPS = 1e-8. Mathworld was helpful too. Just check out "Circle Tangent Line" if you're not sure about your logic.

iamsleepy
New poster
Posts: 4
Joined: Thu Jul 27, 2006 7:50 am
Is there any possible the shortest distance is a line which crosses the circle?
My problem may fail on that condition but I think it' s impossible. The angle must larger than 90 degree.....

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
I agree, that would be impossible...

iamsleepy
New poster
Posts: 4
Joined: Thu Jul 27, 2006 7:50 am
It is just larger than the distance to another tangent line...

P.S.Sorry for my poor English...I can't express myself clearly....

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
I am getting WA. can any one plz give me some cases?

Code: Select all

AC
Last edited by shanto86 on Tue Aug 29, 2006 7:05 am, edited 1 time in total.
Self judging is the best judging!

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
I'm still getting a WA on this, unfortunately...

The following code segment causes an RE, leading me to suspect that the input does not follow the descriptions:

Code: Select all

scanf ( " %Lf %Lf %Lf %Lf %Lf", &mid.x, &mid.y, &r, &b.x, &b.y );

if ( dist ( mid, b ) < r ) {
assert ( 0 );
printf ( "0.000\n" );
continue;
}

mid is the midpoint of the circle and r the radius, b the cartesian house. So it could be that the house is in the tree?

using

Code: Select all

assert ( dist (mid, b) > r || fabs ( dist(mid,b) - r ) < 1e-8 )

also produces the same RE.

So what do AC programs give for this kind of input? My program will unfortunately give a negative number because "distance to tree" is now negative.

Oh, and some interesting test cases:

Code: Select all

3
0 5 5 10 0
0 5 5 10 1
0 5 5 10 -1

Output (from my WA program):

Code: Select all

0.000
1.000
0.000
[/code]

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
Still can't get AC on it.

Can I have an AC's solution output for:

Code: Select all

21
3 4 5 10 1
3 4 5 10 -1
3 4 5 -5 1
0 5 5 6 1
1 4 2 5 5
1 4 2 6 5
1 4 2 4 5
4 4 4 3 3
4 4 4 5 5
4 4 4 6 4
-1 -1 0.01 0 0
5 5 5 0 0
5 0 5 0 0
3 4 5 6 8
3 4 5 6 9
3 4 5 7 8
10 10 14.13 20 20
10 10 14.13 0.1 0.1
10 10 14.13 60 60
10 10 14.13 70 70
10 10 14.13 18 16
My output is:

Code: Select all

2.616
3.602
0.000
1.000
0.000
0.000
0.491
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.831
0.657
0.012
0.000
56.581
70.723
0.000

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
iamsleepy wrote:Is there any possible the shortest distance is a line which crosses the circle?
My problem may fail on that condition but I think it' s impossible. The angle must larger than 90 degree.....
Of course it is possible consider the input:
0 100.1 100 0 200.2
Does anybody know what the expected answer is for this test case? I've got more than 30 WA's on this problem over the last 2 years . I suspect that the my problem is how to account the for:
Note that Cartesians cannot walk through trees.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
wolf wrote:In the problem description: "numbers less than 1 have to be printed without 0 " i.e.: .001 (not 0.001)
Try reading the problem statement again. It says clearly:
A leading zero must be included if and only if the output value is less than 1.000, i.e. 0.123 is a valid output, but .123 is not.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Never mind, got AC at last. They are asking for min(distance to the tree, distance to the closest unsafe location).

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil
Hi,

I've got several WA for this problem. I pass all the I/O I found in this forum and maybe it's just a precision error... Can someone give me the correct output for this random input?

http://www.ecomp.furg.br/~tgoulart/10011.in

This is the output from my program:

http://www.ecomp.furg.br/~tgoulart/my_output.txt