You are given N points in 2D space. You select a set of 3 points, say A, and another point, say B. What is the probability that
- You can draw a unique circle that goes through each point in A
- B lies inside the circle
It should be apparent that a you can brute force all possible choices for points in A. Then, iterate over all the possible choices for B. Now, all we need to check is
- Can you draw a unique circle that passes through the 3 points in A
- If you can, then does B lie inside this circle
To check whether you can draw a unique circle that passes through the 3 points in A, you just need to verify that the 3 points in A are not colinear. This can be done by finding the area of the triangle that passes through the 3 points, and check that this area is non-zero.
This particular check can be done without performing any divisions. As we will see in the rest of this editorial, the solution proposed needs no divisions and avoids any issues with precision.
Given three points that are not collinear, we wish to find the equation of the circle that passes through these 3 points. The general form of the equation of a circle in co-ordinate geometry is
(x2 + y2) + Ax + By + C = 0
Since we already know the co-ordinate of three points that this circle passes through, we already have 3 equations for 3 unknowns A, B and C.
(x12 + y12) + Ax1 + By1 + C = 0 (x22 + y22) + Ax2 + By2 + C = 0 (x32 + y32) + Ax3 + By3 + C = 0
We can use Cramer’s Rule to find the values of A, B and C.
A = | (x12+y12) y1 1 | - | (x22+y22) y2 1 | | (x32+y32) y3 1 | ----------------------- | x1 y1 1 | | x2 y2 1 | | x3 y3 1 |
B = | (x12+y12) x1 1 | | (x22+y22) x2 1 | | (x32+y32) x3 1 | ----------------------- | x1 y1 1 | | x2 y2 1 | | x3 y3 1 |
C = | (x12+y12) x1 y1 | - | (x22+y22) x2 y2 | | (x32+y32) x3 y3 | ----------------------- | x1 y1 1 | | x2 y2 1 | | x3 y3 1 |
substituting these values in the equation above, gives us the following determinant, which is the equation of the circle that passes through 3 points
| (x2 + y2) x y 1 | | (x12+y12) x1 y1 1 | = 0 | (x22+y22) x2 y2 1 | | (x32+y32) x3 y3 1 |
Now, we can put the co-ordinates of chosen point B in the above determinant and perform only integer calculations to find whether the point is inside the circle or not. If the result is 0, the point is on the circle. If the result is of the same sign as the sign of the term (x2 + y2) in the above equation, then the point is outside the circle.
Lastly, I request you to read kuruma’s wonderful post about his experience solving this problem. His approach involved actually finding the co-ordinates of the center of the circle. This works of course, but one has to be very careful to obtain a numerically stable answer.
Can be found here.
Can be found here.