10011 - Where Can You Hide?

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10011 Where Can You Hide - WA

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


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
Location: TORONTO, CANADA

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.

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

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

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.

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

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Mon Jul 31, 2006 3:13 pm

I agree, that would be impossible...

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

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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

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
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

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

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

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 :oops: . 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

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

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
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

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
Last edited by tgoulart on Mon Apr 23, 2007 3:11 pm, edited 1 time in total.
Thiago Sonego Goulart - UFMG/Brazil

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

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

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

Post Reply

Return to “Volume 100 (10000-10099)”