baobab's blog

How to calculate distance between 2 points accurately enough for CodeForces?
By baobab, history, 6 years ago, In English

This is a common subtask in many geometry problems. Today I was unable to solve 1059D because my point-to-point distance calculation is not accurate enough. To summarize the problem, "Find the smallest circle which encompasses all the points, such that its border touches the x axis." I understand there are other ways to solve the problem, but I really want to learn to complete this subtask accurately, since it's recurring in many different problems.

Here's how I would usually calculate it:

double xDist = Math.abs(x1 - x2)
double yDist = Math.abs(y1 - y2)
double dist = Math.sqrt(xDist*xDist + yDist*yDist)

However, this was failing test #4 due to double precision issues. I got some help with this and refactored the calculation into:

double dist = Math.sqrt(xDist) * Math.sqrt(yDist) * Math.sqrt(xDist/yDist + yDist/xDist);

Somehow, this was still not enough. I don't understand how I could possibly calculate distance between 2 points more accurately with Java doubles. Can you help me out? I condensed the failing test case into very little code here.

  • Vote: I like it
  • +28
  • Vote: I do not like it

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

If you just want to compare distances, you can compare squared distances. That way you have no precision error. Often you can solve problems while only taking one sqrt of the squared distance at the end. I'm not sure if this is applicable here though.

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

    I tried this, but still run into the same problem.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      No, you didn't try that. You're comparing and r, and what you should do is compare the squares of there numbers: xDist2 + yDist2 and r2.

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

        Yes I did try it, and no, it doesn't work. I created another minimalist example from test case 4 to prove this: https://pastebin.com/mMvLQwpi

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

          use long long instead of doubles

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

            But the distances can be fractions. For example, test #1 fails when everything is long instead of double. Or maybe you mean only some of the calculations should be in long long, some should be in doubles?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              oh i am wrong, yes distances can be fractions

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

Why the downvotes?

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

using doubles and calculating the dist like you did is perfectly fine for this problem... the precision loss probalby happens somewhere else... (a solution which uses doubles: https://mirror.codeforces.com/contest/1059/submission/44052169)

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

    Did you look at the condensed example case https://pastebin.com/bgDKxiJe ? It shows that the precision loss does indeed occur at the distance calculation. I'm not entirely sure what's going on in the solution you linked, but many solutions to this problem use doubles to do different calculations than point-to-point distances. It looks to me like that solution is also doing something else, not calculating point-to-point distances.

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

I tried a ton of tweaks, and I was able to reduce the error by half!

https://mirror.codeforces.com/contest/1059/submission/44053130

Unfortunately it's still not enough to pass.

The only advice I have for you is switch to C++.

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

    Ouch! In any case thank you for the effort :(

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

      you can even more increase the precision of floating point calculations in java by NOT storing them in variables... (this is weird but ok...) https://mirror.codeforces.com/contest/1059/submission/44053604

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

        So close. Maybe one day far in the future scientists will be able to solve this problem.

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

          44074086 I think I made it quite precise, but the output is 2 times less than it should be...

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

            if (yDist > 1e9) dist = yDist+xDist*xDist/yDist/2;

            Please explain?

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

              Since yDist * yDist doesn't fit in long, I used an approximation if yDist is very large. Though I realized that part is actually where the error is; it should be something like xDist * xDist / 2.0 / yDist, but that gives the answer of about 4.973E13, which is too inaccurate.

              → Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I tried looking at your could but couldn't manage to find the problem. However, I believe that even if you managed to find the precision problem you'd still receive a TLE verdict with this solution, since you do a binary search on the radius and, for every radius, a ternary search on the X coordinate of the center of the circle. It's possible to exclude that ternary search by finding, for every point, an interval of X coordinates of where the center of the circle could be and simply check if the intersection of such intervals is empty or not.

→ Reply
»
6 years ago, # |
  Vote: I like it -28 Vote: I do not like it

If you're having precision issues when measuring distances, first of all you should buy a ruler with a smaller scale. If you're still having trouble, wear glasses and take some medications to prevent your hand from shaking when holding the ruler.

→ Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I was able to get it to test 6 but I have no idea on how to make it more precise (I eliminated the need for ternary search inside the binary search and some other changes). https://mirror.codeforces.com/contest/1059/submission/44082804

Also, why do you have 1400 lines of template?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    The 1400 lines of template is my contest library. I like to keep it in the same file so that I can instantly use anything I need.

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

    I found it!

    double delta = 2 * r * p.y - p.y * p.y;

    p.y is an int and p.y*p.y overflows

    Edit: https://mirror.codeforces.com/contest/1059/submission/44097466

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

      Oh well... That's what happens when you debug something that is hidden under 1400 lines of template that's not yours :P Edit: https://mirror.codeforces.com/contest/1059/submission/44097400 it passed

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

        Sorry about that :( For what it's worth, I did post a minimalist example of the problematic code that didn't have 1400 lines of template (though it was too minimalist to be a CF submission, so I understand why you would rather start working from my CF submission rather than the minimalist example).

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

        I'm not completely sure how this passing solution works, but I guess it's not calculating point to point distances?

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

          It's not. It calculates the range [l, r] in x that the radius can be. If that range is not empty, that radius is ok.

          → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hey, as someone who had similar issues to you, my advice is to not do a<=b to compare very large floating point values.

Why? Because the mantissa will easily cut it off.

Instead of something like a < b, try something like a-b < epsilon where the epsilon is 1e-8 or something. Good luck!

→ Reply