azaxnoot's blog

UVa 12921 ( Triple Shots Help )
By azaxnoot, history, 9 years ago, In English

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 .

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone Help Me Please ? I am waiting .

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you please give me your code??? Your approach is absolutely correct. But I think problem must be probably in comparing double or float values. Another problem may be if one point is midpoint of other two then that point is answer

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Here is my Code : http://ideone.com/p7Pxxo @aayushkapadia

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry for late reply Here is your mistake Line 28: H = H/(calc1); Here don't divide directly . Instead do like this. if(H!=0) H = H/(calc1); Please see in other places also. This is because sometimes it will get 0/0 form if H=0

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Also another problem is use of long long int. I got accepted by use of it

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I remember seeing this problem in a contest, and using equations just like you, and never getting the AC verdict. I would always get WA or RTE (because of some division by 0). Then I thought it would be better find the triangle's circumcenter. The circumcenter (the center of the circumcircle) will be equidistant to the 3 points and is very easy to find.

→ Reply