10649 - Danger Point

football2001 · Post by **football2001** » Thu May 06, 2004 4:59 pm

I get WA for this problem.Who can help me?

[cpp]#include<iostream.h>
#include<math.h>
#include<stdio.h>
#define e 0.0000000000000001

int main()
{
double x,y,b,a,m;
while(1)
{
cin>>x>>y;
if((fabs(x)<e)&&(fabs(y)<e)) break;
m=x*x-sqrt(2)*x*y;
if(x<e||y<e||m<0) printf("INCORRECT INFORMATION !!!\n");
else
{
m=sqrt(m);
b=(-m+sqrt(x*x+sqrt(2)*x*y))/2;
b=y/sqrt(2)+sqrt(b*b-y*y/2);
a=(x-b)*b/y;
printf("%.6lf\n",a);
}
}
return 0;
}[/cpp]

htl · Post by **htl** » Sat May 08, 2004 4:24 pm

I use coordinate geometry to solve this. It's obvious that the four points is on the same circle. Defining the center of the circle as (0.0), I calculate the part in the circle of the line connected between Karim and Rahim. After calculating, I get a formula "s=sqrt(2*(r*r+a*sqrt(2*r*r-a*a)))-a". s is the answer. r is the half of the distance between Jamal and Kamal. And a is the distance between Rahim or Karim and the "danger point". It seems tricky, isn't it? I haven't find out the critical case. Could someone help me?

htl · Post by **htl** » Sat May 08, 2004 4:45 pm

I just solved it... The distance between Karim or Rahim and the danger point could be ZERO...

Noim · Post by **Noim** » Sun May 09, 2004 11:38 pm

i got many many WA for this problem before get AC.
i got many WA in the realtime contest and also in uva online submission.

when i first read this problem i thought that there was a critical input which will be the given data for the distance bewteen the danger poing and Rahim's or Karim's hose may be zero.

and i also thought that if that input is zero i should output INCORRECT INFORMATION !!!

but i got many many WA for that output.

at last i process zero as a legal input and i got AC.

now my question is : if the distace between Karim's house and danger point is zero, CAN IT BE POSSIBLE ....

Their houses stood such a way that the lines connecting Jamal's and Kamal's houses with Rahim are perpendicular; the same applies to Karim

THAT input is zero means that Karim's or Rahim's house is at the danger point. how lines connecting Jamal's and Kamal's houses with danger point are perpendicular while danger point stands on the line connecting Jamal's and Kamal's house ? how can it be possible?

we can think the four terminal point who are passing through a circle and i can get the answer for that input but this input would be contrary to the correct input for this problem statement.

what should be the logic to treat that input as a CORRECT INFORMATION ?

Dominik Michniewski · Post by **Dominik Michniewski** » Mon May 10, 2004 8:10 am

I don't treat such cases specially and got Accepted. I think that you must solve problem without carry about 0-length distance between houses

Best regards
DM

Noim · Post by **Noim** » Mon May 10, 2004 9:04 am

Dominik Michniewski,

what should be the answer if the distance between danger point and karim's house is zero? is it not incorrect information?
what do you think?

if this is in the input file then i think the ouput is not accurate for treating it as legal input. this can be special case. isn't it?

what i think there is such input or similar to this input, in input file. So shouldn't we treat such case specially.

PS: i got AC earlier while i don't treat this specially, i mentioned earlier in this post.

Dominik Michniewski · Post by **Dominik Michniewski** » Mon May 10, 2004 9:14 am

I think that if second data in input is zero, it's still correct value, because it means that houses are placed in one line, with rahim and karim house in the middle of the distance of jamal and kamal houses ... Problem sentence doesn't say, that two persons can't live in one house (maybe it's a big house?)

Best regards
DM

Noim · Post by **Noim** » Mon May 10, 2004 9:29 am

if two people live in same and big house, i have no problem. but ...

1) if the second data is zero , it does not mean they two live in same house as the ouput is not zero in that case. you can see your AC code.

2) if second data is zero (danger points and house of newcomer are same) then how lines connecting Jamal's and Kamal's houses with danger point are perpendicular while danger point stands on the line connecting Jamal's and Kamal's house ?

Their houses stood such a way that the lines connecting Jamal's and Kamal's houses with Rahim are perpendicular; the same applies to Karim

little joey · Post by **little joey** » Mon May 10, 2004 8:32 pm

The problem is still valid for the case that the second input number is zero if you consider it as a limiting case.

Let's call the locations of Jamal and Kamal X and Y resp., the locations of Rahim and Karim P and Q, and the danger point D.
Let's say, without loss of generality, that the second input number is dist(P,D), and that angle(P,D,X)=45deg. The first input number is of course dist(X,Y). There are three different triangles in which P takes part:
triangle(X,Y,P), of which we know that angle(X,P,Y)=90deg;
triangle(X,D,P), of which we know that angle(P,D,X)=45deg;
and triangle(Y,D,P) of which angle(P,D,Y) must be 135deg.

Now look what happens when dist(P,D) gets very small. The three points P, D and X become very close to each other, but still form a very small triangle. Angle(P,D,X) is still 45deg, but since triangle(X,Y,P) is almost flat, angle(P,X,D) is almost 90 degrees. In the limiting case (lim dist(P,D)->0) the three triangles have disappeared, but we can still imagine they are there: the flat triangle(X,Y,P) with angles 0 ,90 and 90 degrees coincides with triangle(Y,D,P) with angles 0, 135 and 45 degrees, and the triangle(X,D,P) with angles 45 ,45 and 90 degrees has completely vanished.

I am not a mathematician, but I think my reasoning is correct.

Noim · Post by **Noim** » Mon May 10, 2004 8:55 pm

i can't understand how can you say that the angle of the triangle (P,X,D) are 45, 45,90 when a distance of (P,D) is zero.

now if the distance(P,D) is zero then the opposite angle angle(P,D,X) must be zero. and other two angles both must be 90 degree but angle (P,D,X) have to be 45 as the problemstatement

now, we can see in other angle.... you wrote....

triangle(X,D,P) with angles 45 ,45 and 90 degrees has completely vanished.

does it vanished means angle(P,D,X) is 45????
if the two angle 45 is same then the opposite sides of this triangle would be same . and then this two sides must be side(X,D) and side(X,P) because side(P,D) is zero. then rest angle(D,P,X) is 90 degree according to your statement. can you think that an angle which is opposite of zero valued side can be 90 degree????

i can't even thing why you can treat this a legal input.
if dis(P,D) is zero, then agnle(P,D,X) can't be 45. because the triangle (P,D,,X) vanished. how can you measure an angle in a vanished triangle.

i think treating is this input is totally insane.

The Second input being ZERO is a just stupid input what i think. and it should be print Incorrect output.

PS: i never solve any problem considering limiting case. even after thinking limiting case , you can't consder here a valid input.

little joey · Post by **little joey** » Tue May 11, 2004 8:32 am

Well, then there's nothing more to convince you, I guess.
But it's not insane, or at least as insane as defining the differential of a function f(x) with respect to x as lim dx->0 df(x)/dx on which half of mathematics is based. Just before dx becomes zero, the quotient still has a value, but for dx=0 the value is undefined.
In this case: Just before dist(P,D) becomes zero triangle(X,D,P) is well formed with angle(P,D,X)=45deg, but when dist(P,D)=0 the three points X, D and P coincide, so the three sides have length zero and the angles are undefined.

I'm out of this discussion. My advise: draw a picture or let someone else explain it to you. I'm not too fond of defending a 'totally insane' problem.