mochow's blog

By mochow, history, 4 years ago, In English,

Here is the problem: http://codeforces.com/problemset/problem/257/C

My approach was this: http://codeforces.com/contest/257/submission/11893523

I first sorted the points clockwise. Then from the last point of the 'clockwise-sorted' array, I go clockwise and counter-clockwise to calculate two angles: Angle1 and Angle2. These two values are actually the summation of the angle between two consecutive points. I output the minimum one.

Eventually, I found out that this problem can be solved in a lot shorter way but I cannot find a bug in my approach.

Was my approach correct? If no, then what did I do wrong? If yes, then how can I get rid of the error = '0.0000388'?

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solution is almost correct, but you are losing precision. Why ? because you are using arccos(x) This involves calculating distance, and then dividing it again by abs(xcoordinate) , all of which contribute to your losses.

My advice is you better off by using arctan(x) because then your precision loss would be minimized ( self explanatory )

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

    How can I use arctan(x) without doing some division? I did this but it is all the same: http://codeforces.com/contest/257/submission/11894858

    I guess I didn't understand the idea of arctan(x).

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

      in arccos(x) you had to find the extra square root (by finding distance) which is precision loss, and again by dividing that value (more precision loss) , but in arctan(x) there is only 1 division.. so that's why...