azaxnoot's blog

By azaxnoot, history, 6 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 .

Read more »

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

By azaxnoot, history, 6 years ago, In English

Hi , Experts .

Can someone please give me some idea about how to solve this problem . The problem link is in Below .

Link : Problem Link

The modulus Part can be solved by BigMod Operation. But how to calculate a^b here . I have not any idea about how to solve this Part more precisely how to optimize this part . Can someone Help me please .

Thanks in Advance .

Read more »

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