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

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

Post by dwyak » Thu Sep 25, 2003 1:14 pm

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

Post by hekacyr » Thu Sep 25, 2003 6:37 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
Location: Bangladesh
Contact:

10011 WA !!! Can anyone Help?

Post by smyazdani » Sat Oct 04, 2003 1:29 pm

[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

Post by nikhil » Wed Oct 08, 2003 1:57 pm

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

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc » Fri May 07, 2004 11:31 pm

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:

Post by skylander » Tue Jun 01, 2004 4:54 pm

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

Post by wolf » Mon Sep 06, 2004 2:45 pm

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

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

10011, help

Post by Yile » Wed Mar 23, 2005 11:19 am

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?

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

Post by Yile » Wed Mar 23, 2005 12:02 pm

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.

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

Post by Yile » Thu Mar 24, 2005 11:36 am

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

Post by JackDaniels » Sat Apr 09, 2005 9:37 am

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.

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

10011

Post by ImLazy » Thu Sep 29, 2005 3:41 am

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

Post by daveon » Thu Jan 05, 2006 11:11 pm

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

Post by kane116 » Wed Jan 11, 2006 6:02 pm

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

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Sun Feb 05, 2006 8:37 am

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

Post Reply

Return to “Volume 100 (10000-10099)”