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