CIRKILL - Editorial

editorial
, , , ,
1

PROBLEM LINK

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Math

PROBLEM

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

QUICK EXPLANATION

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.

EXPLANATION

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.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

6 Likes
2

Thank you @gamabunta for mentioning my post and also for teaching me a new and very cool method with the usage of Cramer’s rule!!! I hope I can keep learning a lot more! :smiley:

2 Likes
3

see this also…same approach lyk kuruma http://www.codechef.com/viewsolution/2334403

4

but how to generate the no of cases for a given input of co-ordinates???

5

There is a direct formula to find the circumcenter of a triangle, then you can equate the radius with the co-ordinates of ASH to find whether or not he comes inside the circle ! simple approach but it lacked arithmetic precision, had to check +/- 10^-6 with radius to get AC !

6

I solved this by finding the equation of 2 perpendicular bisectors by getting slope of perpendiculars and then equation of line (this line passes through the mid-point of the side).then get the co-ordinates of the circumcentre by finding point of intersection of the 2 lines get radius. Then check distance of remaining points from circumcentre to see if it was less than or equal to radius. I was using Python so did not have problem with precision but it might cause problem in other languages. Here is [link to my solution.](point of intersection)

1 Like
7

I tried this problem a lot of times and got WA , I think my approach is right but there is some precision issue, I am writing here my approach and my solution link , please anybody go through my solution and it will nice for me if some one can detect a problem.

Approach :

Select a point (i), and select another three point(j, k, l) and check that the points can form a unique circle or not.

If they can form , than check that point i (arr[i][0], arri) is in the circle or not, if it is in than dead counter will be increased , every time increase the total case counter , than the final answer will be (dead/total) .

My solution link. http://www.codechef.com/viewsolution/2326113

8

In case when x1=x2 (in is_circleformed), notice that x will be nan , i.e not a number (same problem happens whenever the denominator becomes 0 in any of the other case . m1,m2) …so it is giving wa…and also double gave me WA, precision issues i guess, long double worked…

9

Hello @srinu634, double is enough :slight_smile: you can refer to my explanation to see its so… :slight_smile:

10

@upendra1234, your approach is obviously correct, but the way you did those things in terms of precision or not, could make all the difference in AC or WA status… For some precision discussion, check my solution and my non official editorial for this problem :slight_smile:

11

I followed the line intersection approach as given in the above link…

While computing the values of Center’s X coordinate and Center’s Y coordinate I was doing instead of these

double x = (B2C1 - B1C2)/det

double y = (A1C2 - A2C1)/det

I was just doing this

double x = (B2C1 - B1C2)
and
double y = (A1C2 - A2C1)

and suppose the 4th Point is
t1,t2
then the radius is computed by

((t1 * det) - x)^2 + ((t1 * det -y)^2

I dint need to divide the entire numerator by det because while finding another radius it the numerator will again be divided by det again… so I can totally eradicate divion by this process

12

please tell somebody

13

i used basic Geometry to check whether a triangle can be formed or not, then found the center of the circle which passes through these 3 points (i=0, i<n-2, i++ then, j=i+1, j<n-1 ,j++ then k=j+1, k<n, k++ ) then the 4th for loop of l(l!=i or j or k)… let distance b/w l and centre is d… if d<=r(radius) then its counts as Ash catchem’s death :open_mouth:
but wa due to something !?!
@problem setter, does the answer depend on the way the points are given ?!?

14

i also did the same thing (checking whether 3 points form a triangle or not, then finding center and then comparing the distance of 4th point from the center with radius) but got wa, dunno why :open_mouth: