In the land of Chefton there is a trio of killers known as Team Rocket (TR). Chefton is basically a set of tiles, only a single person can stand on a tile at a given instance. Each tile can be described by X and Y co-ordinates describing the position of the tile. For the purpose of this problem, you may assume that a tile does not have any length of breadth. It is only a point.

TR kill in a very unique way. Lets say the three members of the trio stand on the tiles T1, T2, T3 respectively. If a unique circle, say C, can be formed using T1, T2, T3 then all the people standing on the tiles lying within or on the circle C will be killed.

Chefton Intelligence Agency (CIA) send their top agent Ash to Chefton. Let us assume that TR and Ash are standing on random tiles, satisfying the following constraints

All four individuals, the three members of TR and Ash are on different tiles.

There may be several ways in which the four individuals are placed. You may assume that the three members of TR are indistinguishable, while considering how many ways can everyone be placed. Any one of these ways now, is equiprobable. For clarity, refer to the explanation section.

What is the probability that Ash can be killed by Team Rocket.

------ Input ------ 

The first line of the input contains an integer T, the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N, the number of tiles in Chefton. The next N lines consist of 2 space separated integers each, where the i'th line specifies the X and Y co-ordinates of the i'th tile.

------ Output ------ 

For each test case, output a single line containing the probability that Team Rocket kills Ash. Your answer is considered correct if it has an absolute error less than 10^{-6}.

------ Constraints ------ 

1 ≤ T ≤ 10
4 ≤ N ≤ 30
-50 ≤ X, Y ≤ 50
All (X,Y) in a test case are unique.

----- Sample Input 1 ------ 
2
4
-1 0
0 0
0 1
1 0
5
-1 0
0 -1
0 0
0 1
1 0
----- Sample Output 1 ------ 
0.25
0.4
----- explanation 1 ------ 
Test 1: There are 4 ways TR may be placed. Each one of them has the probability 0.25, of occuring.
{ (-1,0), (0,0), (0,1) }, Ash is at (1,0). Ash cannot be killed even though TR has a valid and unique "kill circle".
{ (-1,0), (0,0), (1,0) }, Ash is at (0,1). Ash cannot be killed because TR does not have a unique "kill circle".
{ (-1,0), (0,1), (1,0) }, Ash is at (0,0). Ash can be killed since he is standing inside TR's "kill circle".
{ (0,0), (0,1), (1,0) }, Ash is at (-1,0). Ash cannot be killed even though TR has a valid and unique "kill circle".
Test 2: There are 10 ways TR may be placed. Each one of them has the probability 0.1, of occuring. For each one of those placements, Ash may be placed at one of the 2 remaining positions. Thus, with probability 0.05 each, there are 20 total arrangements to consider. Ash can be killed by TR in 8 of these 20 cases.

Difficulty: MEDIUM_HARD
Tags: Probability

Geometry

Complete search

Mathematics

Matrices
Skill types: Complete search

Starter code:

Solutions:
from itertools import combinations
T = int(input())
while T != 0:
	N = int(input())
	points = []
	for i in range(N):
		(x, y) = map(int, input().strip().split())
		points.append([x, y])
	kill = 0
	total = N * (N - 1) * (N - 2) * (N - 3) / 6
	comb = combinations(points, 3)
	for x in list(comb):
		[x1, y1] = x[0]
		[x2, y2] = x[1]
		[x3, y3] = x[2]
		area = (x1 - x2) * (y2 - y3) - (y1 - y2) * (x2 - x3)
		if area == 0:
			continue
		x12 = x1 - x2
		x13 = x1 - x3
		y12 = y1 - y2
		y13 = y1 - y3
		y31 = y3 - y1
		y21 = y2 - y1
		x31 = x3 - x1
		x21 = x2 - x1
		sx13 = pow(x1, 2) - pow(x3, 2)
		sy13 = pow(y1, 2) - pow(y3, 2)
		sx21 = pow(x2, 2) - pow(x1, 2)
		sy21 = pow(y2, 2) - pow(y1, 2)
		f = (sx13 * x12 + sy13 * x12 + sx21 * x13 + sy21 * x13) / (2 * (y31 * x12 - y21 * x13))
		g = (sx13 * y12 + sy13 * y12 + sx21 * y13 + sy21 * y13) / (2 * (x31 * y12 - x21 * y13))
		c = -pow(x1, 2) - pow(y1, 2) - 2 * g * x1 - 2 * f * y1
		for i in points:
			if i in x:
				continue
			elif pow(i[0], 2) + pow(i[1], 2) + 2 * g * i[0] + 2 * f * i[1] + c <= 1e-06:
				kill = kill + 1
	prob = kill / total
	print(prob)
	T = T - 1


def main():
	t = int(input())
	for testI in range(t):
		n = int(input())
		tiles = []
		for tileI in range(n):
			tiles.append(tuple(map(int, input().split())))
		countPosition = 0
		countKill = 0
		max = len(tiles)
		old1 = None
		old2 = None
		old3 = None
		for chosen in [(tiles[i], tiles[j], tiles[k], tiles[a]) for i in range(max - 2) for j in range(i + 1, max - 1) for k in range(j + 1, max) for a in filter(lambda x: x not in [i, j, k], range(max))]:
			countPosition += 1
			if old1 != chosen[0] or old2 != chosen[1] or old3 != chosen[2]:
				old1 = chosen[0]
				old2 = chosen[1]
				old3 = chosen[2]
				(x1, y1) = chosen[0]
				(x2, y2) = chosen[1]
				(x3, y3) = chosen[2]
				denom = 2 * (x3 * (y1 - y2) + x1 * (y2 - y3) + x2 * (y3 - y1))
				if denom == 0:
					continue
				centerX = (x2 ** 2 * (y3 - y1) + x3 ** 2 * (y1 - y2) + (y2 - y3) * (x1 ** 2 + (y1 - y2) * (y1 - y3))) / denom
				centerY = (x1 * (x2 ** 2 - x3 ** 2 + y2 ** 2 - y3 ** 2) + x3 * (y1 ** 2 - y2 ** 2) + x2 * (x3 ** 2 - y1 ** 2 + y3 ** 2) + (x3 - x2) * x1 ** 2 - x2 ** 2 * x3) / denom
				rSquared = (centerX - chosen[0][0]) ** 2 + (centerY - chosen[0][1]) ** 2
			elif denom == 0:
				continue
			if (centerX - chosen[3][0]) ** 2 + (centerY - chosen[3][1]) ** 2 <= rSquared + 1e-06:
				countKill += 1
		print(countKill / countPosition)
main()


def get_center(A, B, C):
	yDelta_a = B[1] - A[1]
	xDelta_a = B[0] - A[0]
	yDelta_b = C[1] - B[1]
	xDelta_b = C[0] - B[0]
	if xDelta_a == 0:
		T = tuple(C)
		C = tuple(B)
		B = tuple(T)
		yDelta_a = B[1] - A[1]
		xDelta_a = B[0] - A[0]
		yDelta_b = C[1] - B[1]
		xDelta_b = C[0] - B[0]
	if xDelta_b == 0:
		T = tuple(A)
		A = tuple(B)
		B = tuple(T)
		yDelta_a = B[1] - A[1]
		xDelta_a = B[0] - A[0]
		yDelta_b = C[1] - B[1]
		xDelta_b = C[0] - B[0]
	aSlope = yDelta_a / xDelta_a
	bSlope = yDelta_b / xDelta_b
	x = (aSlope * bSlope * (A[1] - C[1]) + bSlope * (A[0] + B[0]) - aSlope * (B[0] + C[0])) / (2 * (bSlope - aSlope))
	if aSlope == 0:
		y = -1 * (x - (B[0] + C[0]) / 2) / bSlope + (B[1] + C[1]) / 2
	else:
		y = -1 * (x - (A[0] + B[0]) / 2) / aSlope + (A[1] + B[1]) / 2
	return (x, y)

def are_collinear(A, B, C):
	if A[0] == B[0] == C[0] or A[1] == B[1] == C[1]:
		return True
	if A[0] == B[0] and C[0] != A[0]:
		return False
	if C[0] == B[0] and C[0] != A[0]:
		return False
	if A[0] == C[0] and C[0] != B[0]:
		return False
	if (A[1] - B[1]) / (A[0] - B[0]) == (A[1] - C[1]) / (A[0] - C[0]):
		return True
	return False
import math
T = int(input())
ans = []
for t in range(T):
	N = int(input())
	points = []
	for i in range(N):
		(x, y) = input().split()
		x = int(x)
		y = int(y)
		points.append((x, y))
	TR_ways = math.factorial(N) / (math.factorial(N - 3) * math.factorial(3))
	propability = 0
	for i in range(N):
		for j in range(i + 1, N):
			for k in range(j + 1, N):
				used = list(points)
				a = points[i]
				b = points[j]
				c = points[k]
				if are_collinear(a, b, c):
					continue
				used.remove(a)
				used.remove(b)
				used.remove(c)
				center = get_center(a, b, c)
				radius = (a[0] - center[0]) ** 2 + (a[1] - center[1]) ** 2
				e = 0
				for item in used:
					if (item[0] - center[0]) ** 2 + (item[1] - center[1]) ** 2 <= radius + 1e-06:
						e += 1 / (N - 3)
				propability += 1 / TR_ways * e
	ans.append(propability)
for item in ans:
	print(item)