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.