10011 - Where Can You Hide?

[dwyak]

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]

the distance to the tree (that whats i meant with min of the distances)

-justus

[smyazdani]

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

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

[GreenPenInc]

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.

[skylander]

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]

In the problem description: "numbers less than 1 have to be printed without 0 " i.e.: .001 (not 0.001)

[Yile]

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]

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]

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]

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.

[ImLazy]

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.

[daveon]

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]

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]

i am also getting wa in this problem.
my algo
1. find the sortest distance from the tree center(tx,ty) to the segment radioactive source (0,0)& cartesian house (px,py). if the distance is greater than radius then print 0.000 and continue;
2. find the tangent lines.
3. measure the distance from (px,py) to the tangents and the tree.
4. output the minimum of them.

can anyone help? thnx