10011 - Where Can You Hide?

iamsleepy · Post by **iamsleepy** » Thu Jul 27, 2006 7:59 am

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;  
}

daveon · Post by **daveon** » Fri Jul 28, 2006 4:41 am

Hi,

An existing thread on this problem already has test cases. Your code fails some of them.

iamsleepy · Post by **iamsleepy** » Fri Jul 28, 2006 5:20 pm

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 · Post by **daveon** » Sat Jul 29, 2006 3:33 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 · Post by **iamsleepy** » Mon Jul 31, 2006 5:04 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 · Post by **daveon** » Mon Jul 31, 2006 3:13 pm

I agree, that would be impossible...

iamsleepy · Post by **iamsleepy** » Mon Jul 31, 2006 3:24 pm

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 · Post by **shanto86** » Tue Aug 15, 2006 3:16 am

I am getting WA. can any one plz give me some cases?

Code: Select all

AC

chrismoh · Post by **chrismoh** » Tue Aug 29, 2006 6:11 am

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 · Post by **chrismoh** » Thu Aug 31, 2006 2:54 pm

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

minskcity · Post by **minskcity** » Thu Aug 31, 2006 7:40 pm

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 · Post by **minskcity** » Thu Aug 31, 2006 8:08 pm

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 · Post by **minskcity** » Thu Aug 31, 2006 8:20 pm

Never mind, got AC at last. They are asking for min(distance to the tree, distance to the closest unsafe location).

tgoulart · Post by **tgoulart** » Wed Dec 20, 2006 7:09 am

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

Thanks in advance!

EDIT: And here is the right output:

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

daveon · Post by **daveon** » Sat Dec 23, 2006 9:11 pm

If you give me your email, I can send you the outputs.

OJ Board

10011 - Where Can You Hide?

10011 Where Can You Hide - WA