PROBLEM LINKDIFFICULTYEASY PREREQUISITESMath PROBLEMYou 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
QUICK EXPLANATIONIt 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
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 nonzero. 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. EXPLANATIONGiven 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 coordinate geometry is (x^{2} + y^{2}) + Ax + By + C = 0 Since we already know the coordinate of three points that this circle passes through, we already have 3 equations for 3 unknowns A, B and C. (x_{1}^{2} + y_{1}^{2}) + Ax_{1} + By_{1} + C = 0 (x_{2}^{2} + y_{2}^{2}) + Ax_{2} + By_{2} + C = 0 (x_{3}^{2} + y_{3}^{2}) + Ax_{3} + By_{3} + C = 0 We can use Cramer's Rule to find the values of A, B and C. A =  (x_{1}^{2}+y_{1}^{2}) y_{1} 1    (x_{2}^{2}+y_{2}^{2}) y_{2} 1   (x_{3}^{2}+y_{3}^{2}) y_{3} 1    x_{1} y_{1} 1   x_{2} y_{2} 1   x_{3} y_{3} 1  B =  (x_{1}^{2}+y_{1}^{2}) x_{1} 1   (x_{2}^{2}+y_{2}^{2}) x_{2} 1   (x_{3}^{2}+y_{3}^{2}) x_{3} 1    x_{1} y_{1} 1   x_{2} y_{2} 1   x_{3} y_{3} 1  C =  (x_{1}^{2}+y_{1}^{2}) x_{1} y_{1}    (x_{2}^{2}+y_{2}^{2}) x_{2} y_{2}   (x_{3}^{2}+y_{3}^{2}) x_{3} y_{3}    x_{1} y_{1} 1   x_{2} y_{2} 1   x_{3} y_{3} 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  (x^{2} + y^{2}) x y 1   (x_{1}^{2}+y_{1}^{2}) x_{1} y_{1} 1  = 0  (x_{2}^{2}+y_{2}^{2}) x_{2} y_{2} 1   (x_{3}^{2}+y_{3}^{2}) x_{3} y_{3} 1  Now, we can put the coordinates 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 (x^{2} + y^{2}) 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 coordinates 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 SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 16 Jul '13, 01:36

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 midpoint of the side).then get the coordinates 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. answered 16 Jul '13, 23:29

but how to generate the no of cases for a given input of coordinates??? answered 16 Jul '13, 20:22

There is a direct formula to find the circumcenter of a triangle, then you can equate the radius with the coordinates 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 ! answered 16 Jul '13, 21:17

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
link
This answer is marked "community wiki".
answered 17 Jul '13, 06:35
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..........
(17 Jul '13, 10:06)
Hello @srinu634, double is enough :) you can refer to my explanation to see its so... :)
(17 Jul '13, 15:00)
@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 :)
(17 Jul '13, 15:01)

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2 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 answered 17 Jul '13, 22:32

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<n2, i++ then, j=i+1, j<n1 ,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 :O but wa due to something !?! @problem setter, does the answer depend on the way the points are given ?!? answered 28 Jul '13, 15:10

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! :D
see this also..same approach lyk kuruma http://www.codechef.com/viewsolution/2334403
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 :O