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: interview

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 )**.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-8: 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)<=10e-6
distance = lambda a, b, c, d, e, f: ((d - a) ** 2 + (e - b) ** 2 + (f - c) ** 2) ** .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)) ** .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):
    '''Returns an integer found by concatenating the indecies of the points in
    the triangle'''
    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):
    '''returns a True if the point is inside a sphere with given center and radius'''
    return radius - distance(point, center) > 1 * 10 ** -10


def distance(point_1, point_2):
    '''Returnse the distance between 2 points in space'''
    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):
    '''Returns the area of the triangle using Heron's Formula'''
    # print(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):
    '''formats the output so it is either a list of 3 points or a
    list of lists of 3 points
    '''
    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)) ** .5

def area(*vertices):
    sides = [distance(*p) for p in combinations(vertices, 2)]
    return (sum(d**2for d in sides)**2 - 2 * sum(d**4for d in sides)) ** .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


# determinant of matrix a
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]


# unit normal vector of plane defined by points a, b, and c
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)**.5
    return x/magnitude, y/magnitude, z/magnitude


# dot product of vectors a and b
def dot(a, b):
    return a[0]*b[0] + a[1]*b[1] + a[2]*b[2]


# cross product of vectors a and b
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


# area of polygon poly
def area(poly):
    if len(poly) < 3:  # not a plane - no area
        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):
    # your code here
    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):

    # Check the points that fall within the sphere
    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 []

    # Check available triangles and save their areas
    point_combinations = list(it.combinations(valid_points, 3))
    areas = []
    for i in point_combinations:
        # Get triangle sides
        a, b, c = dtc(i[0], i[1]), dtc(i[1],i[2]), dtc(i[2],i[0])
        # Get triangle area using Heron's formula
        S = (a+b+c)/2
        areas.append(round((S*(S-a)*(S-b)*(S-c))**0.5, 8))

    # Calculate final variables to be returned
    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]

def biggest_triang_int(points, ce, ra):
    max=0; r=[]; le=len(points); count=0
    for i in range(le):
       for j in range (i+1,le):
          for k in range (j+1,le):
             po=[points[i],points[j],points[k]]
             if distance(po[0],ce)<=ra and distance(po[1],ce)<=ra and distance(po[2],ce)<=ra:
                count+=1
                ae=areatriangle(po[0],po[1],po[2])
                if ae>=max:
                   if abs(ae-max)>1e-5: max=ae; r=[po]
                   else: r.append(po)
    if len(r)==1: r=r[0]
    return [count,max,r] if count>0 else []

def areatriangle((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)):  
    a=distance((x1,y1,z1),(x2,y2,z2))  
    b=distance((x2,y2,z2),(x3,y3,z3))  
    c=distance((x3,y3,z3),(x1,y1,z1))  
    return heron(a,b,c)  

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

def distance((x1,y1,z1),(x2,y2,z2)):    
    return ((x1-x2)**2+(y1-y2)**2+(z1-z2)**2)**.5

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]