UVa 12921 ( Triple Shots Help )

Revision en5, by azaxnoot, 2015-09-08 07:05:58

Hi Experts of CF . Please watch this problem .

Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=862&page=show_problem&problem=4800

I have been trying to solve this Geometry problem from a few Weeks ago . But every time I failed . My approach to solve this problem is ---

As 3 points are in same distance that simply means The point we will found in the result that will be a Center of a Circle whose radius is The distance of those 3 points distinctly. Let 3 points are ( x1, y1, x2, y2, x3 , y3 ). SO , we can write,

(x1 - H)^2 + (y1 - K)^2 = (x2 - H)^2 + (y2 - K)^2 
=> (x1^2 + y1^2 -x2^2 -y2^2) - 2H(x1-x2) - 2K(y1-y2) = 0
=> A - 2HX1 - 2KY1 = 0  ------ ( i )

(x2 - H)^2 + (y2 - K)^2 = (x3 - H)^2 + (y3 - K)^2 
=> (x2^2 + y2^2 -x3^2 -y3^2) - 2H(x2-x3) - 2K(y2-y3) = 0
=> B - 2HX2 - 2KY2 = 0 ------- ( ii )

And then we can Solute this two equation in the following way :

So,
      A - 2HX1 - ( (B - 2HX2) / Y2 ) * Y1 = 0  [ Putting the value of 2K from eqn ( ii ) ]
=>  H = ( AY2 - BY1 ) / ( 2 * ( X1Y2 - X2Y1 ) ) ----- (iii)
And,
=>  K = ( B - 2HX2 ) / 2Y2   ----- ( iv )

Now , if those points are previously Co-Linear then I will print " Impossible " . But If not then we will do the above's Calculation . If ( H, K ) are in the same distance from those 3 points ( x1, y1, x2, y2, x3 , y3 ) the Print ( H, K ) else print " Impossible ".

Is my approach correct ( My code give answers " Impossible " for all test. ) ? If not then why ? Give me some Idea that how can I solve it ?? Thanks in Advance .

Tags uva 12921, geometry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English azaxnoot 2015-09-08 07:05:58 45
en4 English azaxnoot 2015-09-08 07:03:56 3
en3 English azaxnoot 2015-09-08 07:02:17 47
en2 English azaxnoot 2015-09-08 07:01:03 2 Tiny change: ' problem . \nLink : ' -> ' problem .\n \nLink : '
en1 English azaxnoot 2015-09-08 07:00:29 1669 Initial revision (published)