How to calculate distance between 2 points accurately enough for CodeForces?

Revision en2, by baobab, 2018-10-09 21:13:21

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.

Tags #geometry, distance, doubles, precision

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English baobab 2018-10-09 21:13:21 16 Tiny change: 'tebin.com/RzYUZS68).' -> 'tebin.com/bgDKxiJe).'
en1 English baobab 2018-10-09 20:50:16 1328 Initial revision (published)