Wednesday, August 20, 2014

Circle of death


Problem Link : http://www.codechef.com/problems/CIRKILL/

Idea : Given N points , you have to take three points so that a unique circle can be formed . For other point , you have to count these point that is inside the circle or at the perimeter.
First take an int int pair to take point . Take input and store in a vector . Now there are how many ways to choose three point fron given N point ??? Obviously we can find out it with the help of loop . Now we should cheak whether a unique circle can be formed throw the three point or not . To do so , we can cheak the area of the triangle formed by the three points.
The formula to calculate area is-

             Area=x1*(y2-y3)+x2*(y3-y1)+x3(y1-y2)

If the area is not zero , that means a circle can be formed.

Now for other points , we have to count these point that is  inside the circle or at the perimeter. Now a determinant -


| (x2 + y2)  x   y  1 |
| (x12+y12)  x1  y1  1 | = 0
| (x22+y22)  x2  y2  1 |
| (x32+y32)  x3  y3  1 |

given by the general circle equation of the three points and another point that we want to find out.

Now for all cases , solve the determinant . If its value is zero , that means the point is at perimeter of the circle and if the sign of the velue of the determinant is opposite to the area of the triangle , the point is inside the circle . So we got the number of occurning . Now the probablity of the number to all possible cases is our answer .

My Solution : http://pastebin.com/Sqw5PWpW


No comments:

Post a Comment