For a new 3D game that will be released, a team of programmers needs an easy function. (Then it will be processed as a method in a Class, forget this concept for Ruby)

We have an sphere with center O, having in the space the coordinates `[α, β, γ]` and radius `r`  and a list of points, `points_list`, each one with coordinates `[x, y, z]`. Select the biggest triangle (or triangles) that has (have) all its (their) 3 vertice(s) as interior points of the sphere (not even in the sphere contour). You should consider that a point P is interior if its distance to center O, d, is such that:


d < r

and 

(d - r) / r| > 10^(-10)


Let's see the situation with the following points in the image posted below:
```python
A = [1,2,-4]; B = [-3, 2, 4]; C = [7, 8, -4]; D = [2, 3, 5]; E = [-2, -1, 1]
```

The sphere has the following features:
```
O = [1, 2, -2] (Center of the sphere)
radius = 8
```



As C is the only exterior point of the sphere, the possible triangles that have their vertices interior to the sphere are: 

```
ABD, ABE, ADE, BDE
```

Let's see which is the biggest one:

```python
Triangle    Triangle with its points         Area
ABD        [[1,2,-4],[-3,2,4],[2,3,5]]    22.44994432064
ABE        [[1,2,-4],[-3,2,4],[-2,-1,1]]  13.56465996625
ADE        [[1,2,-4],[2,3,5],[-2,-1,1]]   22.62741699796 <---- biggest triangle
BDE        [[-3,2,4],[2,3,5],[-2,-1,1]]   11.31370849898
```

Our function ```biggest_triang_int()``` (javascript: ```biggestTriangInt()```should output for this case:

```python
points_list = [[1,2,-4], [-3, 2, 4], [7, 8, -4], [2, 3, 5], [-2, -1, 1]]
sphere_center = [1, 2, -2]
radius = 8
biggest_triang_int(points_list, sphere_center, radius) == [4, 22.62741699796,  [[1,2,-4],[2,3,5],[-2,-1,1]]]
```

That means that with the given points list we may generate 4 triangles with all their vertices as interior points of the sphere, the biggest triangle has an area of 22.62741699796 (the units does not matter and the values for the area should not be rounded) and finally, there is only one triangle with this maximum value.
Every triangle should be output having the same order of its vertices than in the given list of points. B = [-3,2,4], comes before than D =[2,3,5] and the last one E = [-2,-1,1]
If in the result we have only one triangle, the function should output a list of three points.

Let'see the next case:

```python
points_list = [[1,2,-4], [-3, 2, 4], [7, 8, -4], [2, 3, 5], [-2, -1, 1],
              [3, 2, 6], [1, 4, 0], [-4, -5, -6], [4, 5, 6], [-2, -3, -5],
              [-1, -2, 4], [-3, -2, -6], [-1, -4, 0], [2, 1, -1]]
sphere_center = [0, 0, 0]
radius = 8
biggest_triang_int(points_list, sphere_center, radius) == [165, 33.645207682521445, [[[1, 2, -4], [3, 2, 6], [-1, -4, 0]], [[1, 4, 0], [-1, -2, 4], [-3, -2, -6]]]]
```

Now there are a total of 165 triangles with their vertices in the sphere, the biggest triangle has an area of 33.645207682521445 but we have two triangles with this area value. The vertices of each triangle respect the order of the points list as we expressed before but the additional detail is that the triangles are sorted by the values of the coordinates of their points. Let's compare the coordinates of the first point

```
First point   x  y  z
Triangle1     1  2 -4  <--- this triangle is first in the result
Triangle2     1  4  0
              |  |
              |  y1 < y2 (2, 4)
              |
              x1 = x2     (1 = 1)
```

In the case that all the given points are exterior to the sphere the function should output the empty list.

The points in the list are all valid and each one occurs once.

Remember that if three points are collinear do not form a triangle. For practical purposes you may consider that if the area of a triangle is lower than 10^(-8), the points are aligned.

Enjoy it!

Difficulty: MEDIUM_HARD
Tags: Geometry

String algorithms

Game theory

Mathematics

Data structures
Skill types: Data structures

Starter code:
def biggest_triang_int(points, center, r):
	

Solutions:
from collections import defaultdict
from itertools import combinations

def norme(vect):
	return sum((v ** 2 for v in vect)) ** 0.5

def vectorize(pt1, pt2):
	return [b - a for (a, b) in zip(pt1, pt2)]

def isInCircle(d, r):
	return d < r and (r - d) / r > 1e-10

def crossProd(v1, v2):
	return [v1[0] * v2[1] - v1[1] * v2[0], v1[1] * v2[2] - v1[2] * v2[1], v1[2] * v2[0] - v1[0] * v2[2]]

def biggest_triang_int(point_list, center, radius):
	filteredPts = [pt for pt in point_list if isInCircle(norme(vectorize(pt, center)), radius)]
	dctTriangles = defaultdict(list)
	for threePts in combinations(filteredPts, 3):
		area = abs(norme(crossProd(vectorize(*threePts[:2]), vectorize(*threePts[1:]))) / 2.0)
		if area > 1e-08:
			dctTriangles[area].append(list(threePts))
	maxArea = max(dctTriangles.keys()) if dctTriangles else 0
	return [] if not dctTriangles else [sum(map(len, dctTriangles.values())), maxArea, sorted(dctTriangles[maxArea]) if len(dctTriangles[maxArea]) > 1 else dctTriangles[maxArea][0]]


from itertools import combinations
isclose = lambda a, b: abs(a - b) <= 1e-05
distance = lambda a, b, c, d, e, f: ((d - a) ** 2 + (e - b) ** 2 + (f - c) ** 2) ** 0.5

def biggest_triang_int(points, center, r):
	valid = [i for i in points if distance(*i + center) <= r]
	filter_ = []
	for (a, b, c) in combinations(valid, 3):
		ab = distance(*a + b)
		bc = distance(*b + c)
		ac = distance(*a + c)
		if ab + bc > ac and ab + ac > bc and (bc + ac > ab):
			s = (ab + bc + ac) / 2
			area = (s * (s - ab) * (s - bc) * (s - ac)) ** 0.5
			filter_.append([[a, b, c], area])
	m = max(filter_, key=lambda x: x[1])[1] if filter_ else None
	ans = sorted([i[0] for i in filter_ if isclose(i[1], m)])
	return [len(filter_), m, ans[0] if len(ans) == 1 else ans] if m else []


from math import sqrt
from itertools import combinations

def sort_key(tri_list, tri):
	(x, y, z) = tri
	deg = len(str(len(tri_list)))
	(x_dex, y_dex, z_dex) = (tri_list.index(x), tri_list.index(y), tri_list.index(z))
	return x_dex * 10 ** (3 * deg) + y_dex * 10 ** (2 * deg) + z_dex * 10 ** deg

def in_sphere(point, center, radius):
	return radius - distance(point, center) > 1 * 10 ** (-10)

def distance(point_1, point_2):
	(x_1, y_1, z_1) = tuple(point_1)
	(x_2, y_2, z_2) = tuple(point_2)
	return sqrt((x_2 - x_1) ** 2 + (y_2 - y_1) ** 2 + (z_2 - z_1) ** 2)

def area(p1, p2, p3):
	a = distance(p1, p2)
	b = distance(p1, p3)
	c = distance(p2, p3)
	s = (a + b + c) / 2
	return sqrt(s * (s - a) * (s - b) * (s - c))

def format_output(triangle_list):
	list_out = []
	for item in triangle_list:
		list_out += [list(item)]
	if len(list_out) == 1:
		return list_out[0]
	else:
		return list_out

def biggest_triang_int(point_list, center, radius):
	valid_points = [point for point in point_list if in_sphere(point, center, radius)]
	if len(valid_points) < 3:
		return []
	triangles = [tri for tri in combinations(valid_points, r=3)]
	areas = [[area(tri[0], tri[1], tri[2]), tri] for tri in triangles]
	max_area = max(areas, key=lambda x: x[0])[0]
	num_tri = len(triangles)
	tri_w_max_area = [tri[1] for tri in areas if abs(tri[0] - max_area) < 10 ** (-10)]
	tri_vert = sorted(tri_w_max_area, key=lambda x: sort_key(point_list, x))
	tri_vert = format_output(tri_vert)
	return [num_tri, max_area, tri_vert]


from itertools import combinations

def distance(*pair):
	return sum(((u - v) ** 2 for (u, v) in zip(*pair))) ** 0.5

def area(*vertices):
	sides = [distance(*p) for p in combinations(vertices, 2)]
	return (sum((d ** 2 for d in sides)) ** 2 - 2 * sum((d ** 4 for d in sides))) ** 0.5 / 4

def biggest_triang_int(point_list, center, radius):
	points = [p for p in point_list if distance(center, p) < radius]
	triangles = [[area(*t), list(t)] for t in combinations(points, 3)]
	if not triangles:
		return []
	max_area = max(triangles)[0]
	best_triangles = [t for (a, t) in triangles if a == max_area]
	return [len(triangles), max_area, best_triangles if len(best_triangles) > 1 else best_triangles.pop()]


from itertools import combinations
from math import sqrt

def det(a):
	return a[0][0] * a[1][1] * a[2][2] + a[0][1] * a[1][2] * a[2][0] + a[0][2] * a[1][0] * a[2][1] - a[0][2] * a[1][1] * a[2][0] - a[0][1] * a[1][0] * a[2][2] - a[0][0] * a[1][2] * a[2][1]

def unit_normal(a, b, c):
	x = det([[1, a[1], a[2]], [1, b[1], b[2]], [1, c[1], c[2]]])
	y = det([[a[0], 1, a[2]], [b[0], 1, b[2]], [c[0], 1, c[2]]])
	z = det([[a[0], a[1], 1], [b[0], b[1], 1], [c[0], c[1], 1]])
	magnitude = (x ** 2 + y ** 2 + z ** 2) ** 0.5
	return (x / magnitude, y / magnitude, z / magnitude)

def dot(a, b):
	return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]

def cross(a, b):
	x = a[1] * b[2] - a[2] * b[1]
	y = a[2] * b[0] - a[0] * b[2]
	z = a[0] * b[1] - a[1] * b[0]
	return (x, y, z)

def area(poly):
	if len(poly) < 3:
		return 0
	total = [0, 0, 0]
	for i in range(len(poly)):
		vi1 = poly[i]
		if i is len(poly) - 1:
			vi2 = poly[0]
		else:
			vi2 = poly[i + 1]
		prod = cross(vi1, vi2)
		total[0] += prod[0]
		total[1] += prod[1]
		total[2] += prod[2]
	result = dot(total, unit_normal(poly[0], poly[1], poly[2]))
	return [abs(result / 2), poly]

def distance(a, b):
	pow_each = [pow(x, 2) for x in map(lambda x, y: x - y, a, b)]
	sum_all = sum(pow_each)
	return sqrt(sum_all)

def out_side(point, c, r):
	return distance(point, c) <= r

def all_max(elements, key):
	if not elements:
		return (0, [])
	value = max(elements, key=key)[0]
	results = [j for (i, j) in elements if i == value]
	return (value, results if len(results) > 1 else results[0])

def biggest_triang_int(point_list, center, radius):
	valid_points = [x for x in point_list if out_side(x, center, radius)]
	comb_elements = list(combinations(valid_points, 3))
	results = [area(x) for x in list(map(list, comb_elements))]
	(result, poly) = all_max(results, key=lambda x: x[0])
	return [len(comb_elements), result, poly] if results else []


import itertools

def in_sphere(point, center, radius):
	dist = sum([(p - r) ** 2 for (p, r) in zip(point, center)])
	dist = dist ** 0.5
	return dist < radius and abs(dist - radius) / radius > 1e-10

def area(triangle_vertices):
	l1 = sum(((triangle_vertices[0][i] - triangle_vertices[1][i]) ** 2 for i in range(3))) ** 0.5
	l2 = sum(((triangle_vertices[0][i] - triangle_vertices[2][i]) ** 2 for i in range(3))) ** 0.5
	l3 = sum(((triangle_vertices[1][i] - triangle_vertices[2][i]) ** 2 for i in range(3))) ** 0.5
	p = (l1 + l2 + l3) / 2
	A = (p * (p - l1) * (p - l2) * (p - l3)) ** 0.5
	return A

def biggest_triang_int(point_list, center, radius):
	interior_points = [p for p in point_list if in_sphere(p, center, radius)]
	Triangles = []
	for triplet in itertools.combinations(interior_points, 3):
		Triangles.append((list(triplet), area(triplet)))
	num_tri = len(Triangles)
	if num_tri < 1:
		return []
	max_a = max(Triangles, key=lambda x: x[1])[1]
	winners = [T[0] for T in Triangles if abs(T[1] - max_a) < 0.01]
	if len(winners) == 1:
		return [num_tri, max_a, winners[0]]
	else:
		return [num_tri, max_a, winners]
	return 4


import itertools as it

def biggest_triang_int(point_list, center, radius):
	dtc = lambda p1, p2: sum([(i - j) ** 2 for (i, j) in zip(p1, p2)]) ** (1.0 / 2)
	valid_points = [point for point in point_list if dtc(center, point) < radius]
	if len(valid_points) == 0:
		return []
	point_combinations = list(it.combinations(valid_points, 3))
	areas = []
	for i in point_combinations:
		(a, b, c) = (dtc(i[0], i[1]), dtc(i[1], i[2]), dtc(i[2], i[0]))
		S = (a + b + c) / 2
		areas.append(round((S * (S - a) * (S - b) * (S - c)) ** 0.5, 8))
	(pot_triangles, max_area, max_triangle_points) = (len(areas), max(areas), [])
	if areas.count(max(areas)) == 1:
		max_triangle_points = list(point_combinations[areas.index(max(areas))])
	else:
		for c in range(areas.count(max(areas))):
			max_triangle_points.append([i for i in point_combinations[areas.index(max(areas))]])
			del point_combinations[areas.index(max(areas))]
			del areas[areas.index(max(areas))]
	return [pot_triangles, max_area, max_triangle_points]


from itertools import *
from math import sqrt

def area_triang(a, b, c):
	s = (a + b + c) / 2
	return sqrt(s * (s - a) * (s - b) * (s - c))

def calc_area(triangle):
	(A, B, C) = triangle
	c = sqrt(distance_sq(A, B))
	b = sqrt(distance_sq(A, C))
	a = sqrt(distance_sq(B, C))
	return area_triang(a, b, c)

def distance_sq(point1, point2):
	(x1, y1, z1) = point1
	(x2, y2, z2) = point2
	return (x1 - x2) ** 2 + (y1 - y2) ** 2 + (z1 - z2) ** 2

def combin(point_list, i):
	return combinations(point_list, i)

def is_point_in_sphere(vert, center, r):
	dd = distance_sq(vert, center)
	return dd - r ** 2 < 0 and abs((sqrt(dd) - r) / r) > pow(10, -10)

def to_tup(point_list):
	point_list_ = []
	for point in point_list:
		point_list_.append(tuple(point))
	return point_list_

def triang_to_list(triang):
	(pointA, pointB, pointC) = triang
	return [list(pointA), list(pointB), list(pointC)]

def triangs_tolist(triang_list):
	res = []
	for triang in triang_list:
		res.append(triang_to_list(triang))
	return res

def biggest_triang_int(point_list, center, radius):
	point_list_ = []
	for point in point_list:
		if not is_point_in_sphere(point, center, radius):
			continue
		point_list_.append(point)
	point_list_ = to_tup(point_list_)
	triangs_area = {}
	for comb in combin(point_list_, 3):
		triangle = tuple(comb)
		area = calc_area(triangle)
		if area < pow(10, -8):
			continue
		triangs_area[triangle] = area
	num_triangs = len(triangs_area)
	if num_triangs == 0:
		return []
	max_area = max(triangs_area.values())
	res = [num_triangs, max_area]
	sol = []
	for (triang, area) in triangs_area.items():
		if abs((area - max_area) / area) < pow(10, -10):
			sol.append(list(triang))
	if len(sol) == 1:
		sol_one = triang_to_list(sol[0])
		res.append(sol_one)
		return res
	else:
		sol_plus = triangs_tolist(sol)
		res.append(sol_plus)
	sol_plus.sort()
	return res


import math

def dis_cal(start_pnt, end_pnt):
	return math.sqrt((end_pnt[0] - start_pnt[0]) ** 2 + (end_pnt[1] - start_pnt[1]) ** 2 + (end_pnt[2] - start_pnt[2]) ** 2)

def filter_points(point_list, center, radius):
	fnl_pnt = []
	for pnt in point_list:
		dis = dis_cal(center, pnt)
		if dis < radius and (dis - radius) / radius > 2.718281828459045 - 10:
			fnl_pnt.append(pnt)
	return fnl_pnt

def triangle_exist(points, triangle_lst):
	for tria_lst in triangle_lst:
		if points[0] in tria_lst[0] and points[1] in tria_lst[0] and (points[2] in tria_lst[0]):
			return False
	return True
from itertools import combinations

def find_triangles(point_list):
	fnl_pnt = []
	max_val = 0
	for (i, j, k) in combinations(point_list, 3):
		ab = dis_cal(i, j)
		bc = dis_cal(j, k)
		ac = dis_cal(k, i)
		if ab + bc > ac and ab + ac > bc and (bc + ac > ab):
			ab_vec = [j[0] - i[0], j[1] - i[1], j[2] - i[2]]
			ac_vec = [k[0] - i[0], k[1] - i[1], k[2] - i[2]]
			area = math.sqrt((ab_vec[1] * ac_vec[2] - ac_vec[1] * ab_vec[2]) ** 2 + (ab_vec[0] * ac_vec[2] - ac_vec[0] * ab_vec[2]) ** 2 + (ab_vec[0] * ac_vec[1] - ac_vec[0] * ab_vec[1]) ** 2)
			if area > 2.718281828459045 - 8:
				fnl_pnt.append(([i, j, k], area / 2))
				if area / 2 > max_val:
					max_val = area / 2
	max_traingle = []
	for i in fnl_pnt:
		if i[1] == max_val:
			max_traingle.append(i[0])
	return (len(fnl_pnt), max_traingle, max_val)

def biggest_triang_int(point_list, center, radius):
	interior_points = filter_points(point_list, center, radius)
	(num_triangle, max_triangles, max_val) = find_triangles(interior_points)
	if len(max_triangles) == 1:
		max_triangles = max_triangles[0]
	if num_triangle == 0:
		return []
	return [num_triangle, max_val, max_triangles]