10011 - Where Can You Hide?

Moderator: Board moderators

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:
if the distance from the house to the tree is shorter than the distance to the left & right tangent, should i output the distance as the distance from house to the tree or others.

hekacyr
New poster
Posts: 7
Joined: Sat Oct 19, 2002 1:25 pm
the distance to the tree (that whats i meant with min of the distances)

-justus

smyazdani
New poster
Posts: 1
Joined: Sat Oct 04, 2003 1:05 pm
Contact:

10011 WA !!! Can anyone Help?

[cpp]
#include<stdio.h>
#include<math.h>

void main()
{
//freopen("10011.txt","rt",stdin);
double x1,y1,r,x2,y2,r1,o1,o,o2,r2,dis,temp,ox,x;
double pi=3.1415926535897932384626433832795;
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf%lf",&x1,&y1,&r,&x2,&y2);
r1=sqrt(x1*x1+y1*y1);
o1=asin(y1/r1);
o1=o1*180/pi;
o=asin(r/r1);
o=o*180/pi;
r2=sqrt(x2*x2+y2*y2);
o2=asin(y2/r2);
o2=o2*180/pi;
if(x2*x1<0)
if(x2<0)
o2=180-o2;
else if(x1<0)
o1=180-o1;
dis=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
temp=r1*cos(o*pi/180);
if(o2>=o1+o || o2<=o1-o)
x=0;
else if(dis<=r)
x=0;
else if(r2<=temp)
x=0;
else
{
temp=fabs(o1-o2);
ox=o-temp;
x=r2*sin(ox*pi/180);
}
if(dis-r<x)
x=dis-r;
x+=0.00005;
printf("%.3lf\n",x);
}
}
[/cpp]

I have tried all possible cases that came in my mind, But still got WA. Can anyone help me?

9
5 5 5 11 5
5 5 5 0.1 6.42
5 5 5 0.1 5.998
5 5 5 0.0005 10
20 -24 6 25 -30
5 5 1 12 12
20 0 3 7 -7
-9.6 4.3 2.1 -19.2 7.9
-10 2 5 -18 -2

For these input cases my program generates:

1.000
0.100
0.001
0.001
1.810
2.400
0.000
3.517
3.676

nikhil
New poster
Posts: 11
Joined: Wed Oct 08, 2003 1:37 pm

help me

10011
Where Can You Hide?
please somebody help me to solve.
thanks

GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:
I think I have it solved; it handles the given test data and the special cases I throw at it without a hitch. How are we to handle the case where the tree just touches the origin (radiation source)? I have it so that the half of the plane with the tree in it is protected and the other half is not. Can anyone who got AC on this give me some difficult test data and answers please? I can also post my code if that would help.
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

skylander
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:
i tried my program with many test cases and i am still getting wa from the judge...wonder wad i have overlooked...i considered the house being nearer to the source than the tree (pythagoras theorem), the house being out of range of the radiation (by the angle between tree, house and source)...and using long doubles for computation....my formula for calculating distance of house and the nearest tangent works for all my test cases, and i also considered if the house is nearer to the tree or to the tangents.....can any1 provide me with test data to test my program...thx..

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
In the problem description: "numbers less than 1 have to be printed without 0 " i.e.: .001 (not 0.001)

Yile
New poster
Posts: 17
Joined: Sun Feb 27, 2005 10:36 am
Location: China

10011, help

Input:

Code: Select all

``````9
5 5 1 12 12
20 0 3 7 -7
-9.6 4.3 2.1 -19.2 7.9
5 5 5 11 5
5 5 5 0.1 6.42
5 5 5 0.1 5.998
5 5 5 0.0005 10
20 -24 6 25 -30
-10 2 5 -18 -2
``````
My output:

Code: Select all

``````2.400
0.000
3.517
1.000
0.100
0.001
0.001
1.810
3.676
``````
Is that right?
Can anyone give me some more test IO?

Yile
New poster
Posts: 17
Joined: Sun Feb 27, 2005 10:36 am
Location: China
Another question:
If the result is 0.00000001, should I print 0.000 of 0.001? I mean though the distance is very little, but at least it exists. And 0.000 means the house can not be protected. That is not suitable to the distance less than 0.0005.

Yile
New poster
Posts: 17
Joined: Sun Feb 27, 2005 10:36 am
Location: China
Please read my algorithm, and help me to find the bug, or if it losts precision.

Code: Select all

``````/*all the datas are of long double type*/
infinity=9999999999;
if(x_tree==0)
k_tree=infinity;
else
k_tree=y_tree/x_tree;
if(k_tree==infinity)
{
k_R=sqrt(y_tree*y_tree-r_tree*r_tree)/r_tree;
k_L=k_R*-1.0;
/*k_L and k_R are the slope of the left and right tangents*/
/*the left tangent is on the counter-clockwise side of the tree*/
}
else
{
tan=r_tree/sqrt(x_tree*x_tree+y_tree*y_tree-r_tree*r_tree);
if((x_tree==r_tree || x_tree==r_tree*-1.0) && x_tree*y_tree>0)
k_L=infinity;
else
k_L=(k_tree+tan)/(1.0-k_tree*tan);
/*tan(a+b)=[tan(a)+tan(b)]/[1-tan(a)*tan(b)]*/
if((x_tree==r_tree || x_tree==r_tree*-1.0) && x_tree*y_tree<0)
k_R=infinity;
else
k_R=(k_tree-tan)/(1.0+k_tree*tan);
/*tan(a-b)=[tan(a)-tan(b)]/[1+tan(a)*tan(b)]*/
}
if(x_house==0)
k_house=infinity;
else
k_house=y_house/x_house;
/*To check if the answer is 0.000, as follows. There are 4 cases*/
if(x_house*x_tree<=0 && y_house*y_tree<=0)
printf("0.000\n");
else if(k_L<=0 && k_R>=0 && k_house>=k_L && k_house<=k_R)
printf("0.000\n");
else if(!(k_L<=0 && k_R>=0) && (k_house>=k_L || k_house<=k_R))
printf("0.000\n");
else if(sqrt(x_house*x_house+y_house*y_house)<=r_tree/tan)
printf("0.000\n");
/*Now begin to calculate the distance.*/
/*There are 3 distances to choose from:
dis1: to the left tangent
dis2: to the right tangent
dis_tree: to the tree*/
if(k_L==infinity)
dis1=x_house>0?x_house:(-1.0*x_house);
else
{
intercept=y_house-k_L*x_house;
/*y=k*x+b --> b=y-k*x*/
if(intercept<0)
intercept*=-1.0;
dis1=intercept/sqrt(1.0+k_L*k_L);
/*d=|b|*cos(a), cos(a)=1/sqrt(1+tan(a)^2)*/
}
if(k_R==infinity)
dis2=x_house>0?x_house:(-1.0*x_house);
else
{
intercept=y_house-k_R*x_house;
if(intercept<0)
intercept*=-1.0;
dis2=intercept/sqrt(1.0+k_R*k_R);
}
dis_tree=sqrt((y_house-y_tree)*(y_house-y_tree)+(x_house-x_tree)*(x_house-x_tree))-r_tree;
/*Then output the minimal of the three*/
printf("%.3lf\n",min(dis1,dis2,dis_tree));
``````
Thanks.

JackDaniels
New poster
Posts: 8
Joined: Mon Aug 11, 2003 4:51 pm
Location: Suceava, Romania
Hi Yile!

I've wrote the code for this problem many times and I really don't know where is my mistake, cause I've got WA many times also.
Here is the link to an image for a little explanation in solving the problem:
http://apollo.eed.usv.ro/~lamasanu_i/10011_2.PNG

I've got this output for your input:

Code: Select all

``````1.000
0.100
0.001
0.001
1.810
2.400
0.000
3.517
3.000
``````
I'm getting WA for this output also.
Nothing is lost because everything is transforming.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

10011

I think the most important thing of this problem is precision. And the main point is to know the vector of the two tangents. I calculated the slope of the two tangents, which is (x*y+(or -)r*sqrt(x^2+y^2-r^2))/(x^2-r^2), while x,y is the center of the tree, r is the radii. But this formula brings me Wrong Answer.
Who have any other good algorithms. Can you help me? Thanks.
I stay home. Don't call me out.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Becareful of how you check if a point is within two tangent lines.

Code: Select all

``````4
5 5 6 12 12
-5 5 6 -12 12
-5 -5 6 -12 -12
5 -5 6 12 -12
``````

Code: Select all

``````3.899
3.899
3.899
3.899
``````

kane116
New poster
Posts: 8
Joined: Sun Aug 07, 2005 5:35 am
I find the points of the tangent on the circle, the two equation for finding the points is:
(x - t.x) ^ 2 + (y - t.y) ^ 2 = r ^ 2
p.x ^ 2 + p.y ^ 2 = t.x ^2 + t.y ^ 2 - r ^ 2

t.x & t.y is centre of the tree,
p.x & p.y is the point of the tangent on the circle.

However, I still got WA, I don't know what's wrong with my code...

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm