10011  Where Can You Hide?
Moderator: Board moderators
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=180o2;
else if(x1<0)
o1=180o1;
dis=sqrt((x1x2)*(x1x2)+(y1y2)*(y1y2));
temp=r1*cos(o*pi/180);
if(o2>=o1+o  o2<=o1o)
x=0;
else if(dis<=r)
x=0;
else if(r2<=temp)
x=0;
else
{
temp=fabs(o1o2);
ox=otemp;
x=r2*sin(ox*pi/180);
}
if(disr<x)
x=disr;
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
#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=180o2;
else if(x1<0)
o1=180o1;
dis=sqrt((x1x2)*(x1x2)+(y1y2)*(y1y2));
temp=r1*cos(o*pi/180);
if(o2>=o1+o  o2<=o1o)
x=0;
else if(dis<=r)
x=0;
else if(r2<=temp)
x=0;
else
{
temp=fabs(o1o2);
ox=otemp;
x=r2*sin(ox*pi/180);
}
if(disr<x)
x=disr;
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

 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!"
"Finally I have freed myself from the clutches of the garbage fairy!"
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..
10011, help
Input:
My output:
Is that right?
Can anyone give me some more test IO?
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
Code: Select all
2.400
0.000
3.517
1.000
0.100
0.001
0.001
1.810
3.676
Can anyone give me some more test IO?
Please read my algorithm, and help me to find the bug, or if it losts precision.
Thanks.
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_treer_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 counterclockwise side of the tree*/
}
else
{
tan=r_tree/sqrt(x_tree*x_tree+y_tree*y_treer_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.0k_tree*tan);
/*tan(a+b)=[tan(a)+tan(b)]/[1tan(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_treetan)/(1.0+k_tree*tan);
/*tan(ab)=[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_housek_L*x_house;
/*y=k*x+b > b=yk*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_housek_R*x_house;
if(intercept<0)
intercept*=1.0;
dis2=intercept/sqrt(1.0+k_R*k_R);
}
dis_tree=sqrt((y_housey_tree)*(y_housey_tree)+(x_housex_tree)*(x_housex_tree))r_tree;
/*Then output the minimal of the three*/
printf("%.3lf\n",min(dis1,dis2,dis_tree));

 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:
I'm getting WA for this output also.
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
Nothing is lost because everything is transforming.
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^2r^2))/(x^2r^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.
Who have any other good algorithms. Can you help me? Thanks.
I stay home. Don't call me out.
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
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...
(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...

 New poster
 Posts: 42
 Joined: Fri Jun 13, 2003 3:47 pm
 Location: Dhaka , Bangladesh
 Contact:
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
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