We need a function that may receive a list  of an unknown amount of points in the same plane, having each of them, cartesian coordinates of the form (x, y) and may find the biggest triangle (the one with the largest area) formed by all of the possible combinations of groups of three points of that given list.
Of course, we will have some combinations of three points that does not form a triangle, because the three points are aligned.
The function find_biggTriang(listOfPoints), will output a list with the following data in the order presented bellow:
```python
[(1), (2), (3), (4), 5]

(1) - Number of points received (You may assume that you will not receive duplicates)

(2) - Maximum possible amount of triangles that can be formed with the amount of received 
      points (number in data (1) above). It should be expressed as an integer, (no L for long type 
      variables)

(3) - Real Number of triangles that can be formed with the given points. (The function should have a 
      counter for all the cases of three points aligned). It should be expressedas as an integer.

(4) - The triangles that have maximum area in a sorted list. 
      If there are two triangles with the biggest area, the result will be presented in this way:
      [[[xA1, yA1], [xB1, yB1], [xC1, yC1]], [[xA2, yA2], [xB2, yB2], [xC2, yC2]]]
      But if we have only one triangle with max. area, there is no need of a spare level of braces, 
      so it will be as follows: [[xA1, yA1], [xB1, yB1], [xC1, yC1]]

(5) - The value of max. area (absolute value) that was found as a float. As we did not define the 
      units of length for the coordinates, the units for the area will be ignored.

```

It would be useful to apply the expression for the area of a triangle with vertices A, B, and C, is equal to the half of the determinant of the matrix, using the respective coordinates as follows:

```python

                               | xA    yA    1|
Area Triangle(A, B, C) = 1/2 . | xB    yB    1|
                               | xC    yC    1|

```
The negative sign for the area should be ignored for the purpose of the exercise, and we will consider the absolute value for all cases.

See how to calculate the determinant of a matrix 3 x 3, rule of Sarrus.
https://en.wikipedia.org/wiki/Rule_of_Sarrus

Using this expression, it would be easy to detect the cases when three points are aligned.

Let's see some simple cases.
```python
listOfPoints1 = [(0, 1), (7, 3), (9, 0), (7, 10), (2, 9), (10, 7), (2, 8), (9, 8), (4, 4), (2, 10), (10, 1), (0, 4), (4, 3), (10, 0), (0, 3), (3, 4), (1, 1), (7, 2), (4, 0)] (19 points received)

find_biggTriang(listOfPoints1) --------> [19, 969, 953, [[0, 1], [7, 10], [10, 0]], 48.5]

/// Combinations (19, 3) = 969 (We do not have repeated points)
   953 real cases for triangles because the function detected 16 cases when three points are       
   aligned.
   The function found one triangle [[0, 1], [7, 10], [10, 0]] with its area equals to 49.5///

listOfPoints2 = [(7, 4), (0, 0), (9, 10), (5, 0), (8, 1), (7, 6), (9, 3), (2, 4), (6, 3), (5, 6), (3, 6), (10, 0), (9, 7), (3, 10), (10, 2)] (15 points received)

find_biggTriang(listOfPoints2) --------> [15, 455, 446, [[[0, 0], [9, 10], [10, 0]], [[0, 0], [10, 0], [3, 10]]], 50.0]

/// Combinations(15, 3) = 455 but there were only 446 real triangles
   We found two triangles: [[0, 0], [9, 10], [10, 0]] and [[0, 0], [10, 0], [3, 10]] (both in a 
   sorted list. Both triangles have an area of 50.0///
```
Your code will be tested with lists created randomly up to 70 points.

Have a nice moment and enjoy it!!

Difficulty: EASY
Tags: Fundamentals

Sorting

Complete search

Mathematics

Data structures
Skill types: Sorting

Data structures

Complete search

Starter code:
def find_biggTriang(points):
	

Solutions:
from itertools import combinations

def area(t):
	((a, b), (c, d), (e, f)) = t
	return abs(a * d + b * e + c * f - d * e - a * f - b * c) / 2

def find_biggTriang(lst):
	tris = list(combinations(lst, 3))
	areas = list(map(area, tris))
	m = max(areas)
	mTris = [list(map(list, t)) for (t, v) in zip(tris, areas) if v == m]
	return [len(lst), len(tris), sum(map(bool, areas)), mTris if len(mTris) != 1 else mTris.pop(), m]


from itertools import combinations as com
from collections import defaultdict

def area(points):
	((ax, ay), (bx, by), (cx, cy)) = points
	return abs(ax * (by - cy) + bx * (cy - ay) + cx * (ay - by)) / 2

def find_biggTriang(listPoints):
	allcom = [[[j[0], j[1]] for j in i] for i in set(com(listPoints, 3))]
	aaa = defaultdict(list)
	count = 0
	for i in allcom:
		ar = area(i)
		if ar != 0:
			count += 1
			aaa[ar].append(i)
	maxarea = max(set(aaa.keys()))
	po = aaa[maxarea]
	if len(po) == 1:
		po = po[0]
	return [len(listPoints), len(allcom), count, po, maxarea]


from itertools import combinations

def find_biggTriang(points):
	num_triplets = num_triangles = 0
	(max_area, max_triangles) = (0, [])
	for triangle in map(list, combinations(map(list, points), 3)):
		num_triplets += 1
		((ax, ay), (bx, by), (cx, cy)) = triangle
		area = abs(ax * (by - cy) + bx * (cy - ay) + cx * (ay - by)) / 2
		if not area:
			continue
		num_triangles += 1
		if area > max_area:
			(max_area, max_triangles) = (area, [])
		if area == max_area:
			max_triangles.append(triangle)
	return [len(points), num_triplets, num_triangles, max_triangles.pop() if len(max_triangles) == 1 else max_triangles, max_area]


def find_biggTriang(ps):
	n = len(ps)
	count = 0
	max_area = -1.0
	max_area_triangles = []
	for i in xrange(n):
		for j in xrange(i + 1, n):
			(dx1, dy1) = (ps[j][0] - ps[i][0], ps[j][1] - ps[i][1])
			for k in xrange(j + 1, n):
				(dx2, dy2) = (ps[k][0] - ps[i][0], ps[k][1] - ps[i][1])
				a = abs(0.5 * (dx1 * dy2 - dx2 * dy1))
				count += a != 0
				if a < max_area:
					continue
				triangle = [ps[i], ps[j], ps[k]]
				if a > max_area:
					max_area = a
					max_area_triangles = [triangle]
				elif a == max_area:
					max_area_triangles.append(triangle)
	max_area_triangles = [map(list, tr) for tr in max_area_triangles]
	if len(max_area_triangles) == 1:
		max_area_triangles = max_area_triangles[0]
	return [n, n * (n - 1) * (n - 2) // 6, count, max_area_triangles, max_area]


from itertools import combinations

def dist(a, b):
	return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

def triangle_area(A, B, C):
	(a, b, c) = sorted([dist(A, B), dist(A, C), dist(B, C)])
	if a + b > c and c - a < b:
		s = round(((a + b + c) * (a + b - c) * (a + c - b) * (b + c - a)) ** 0.5 / 4, 1)
	else:
		s = None
	return s

def find_biggTriang(listPoints):
	num_points = len(listPoints)
	possible_count = 0
	real_count = 0
	areas = {}
	max_area = 0
	for x in combinations(listPoints, 3):
		possible_count += 1
		area = triangle_area(*x)
		if area:
			areas[x] = area
			max_area = max(max_area, area)
			real_count += 1
	max_triangles = [list(map(list, k)) for (k, v) in list(areas.items()) if v == max_area]
	if len(max_triangles) == 1:
		max_triangles = max_triangles[0]
	return [num_points, possible_count, real_count, max_triangles, max_area]


def area_triangel(i):
	return abs(1 / 2 * (i[0][0] * i[1][1] + i[0][1] * i[2][0] + i[1][0] * i[2][1] - i[2][0] * i[1][1] - i[2][1] * i[0][0] - i[1][0] * i[0][1]))

def find_biggTriang(listPoints):
	import itertools
	max_points = []
	max_area = -1000
	every_valid_point = list(itertools.combinations(listPoints, 3))
	num_invalid_points = 0
	for j in every_valid_point:
		area = area_triangel(j)
		if area == 0:
			num_invalid_points += 1
		elif area > max_area:
			(max_area, max_points) = (area, [])
			max_points.append(list((list(x) for x in j)))
		elif area == max_area:
			max_points.append(list((list(x) for x in j)))
	return [len(listPoints), len(every_valid_point), len(every_valid_point) - num_invalid_points, max_points[0] if len(max_points) == 1 else max_points, max_area]


from itertools import combinations
from numpy.linalg import det

def find_biggTriang(listP):
	lp = list(map(list, listP))
	result = [0, 0, 0, [], 0]
	result[0] = len(lp)
	lc = list(combinations(lp, 3))
	result[1] = len(lc)
	n = 0
	for c in lc:
		l = list(c)
		m = [[l[0][0], l[0][1], 1], [l[1][0], l[1][1], 1], [l[2][0], l[2][1], 1]]
		A = round(1 / 2 * abs(det(m)), 1)
		if A == 0:
			n += 1
		elif A == result[4]:
			result[3].append(l)
		elif A > result[4]:
			result[4] = A
			result[3].clear()
			result[3].append(l)
	result[2] = result[1] - n
	result[3] = sorted(result[3])
	if len(result[3]) == 1:
		result[3] = result[3][0]
	return result


from itertools import combinations

def find_biggTriang(listPoints):
	s = combinations(listPoints, 3)
	j = 0
	i = 0
	ret = []
	mx = 0
	for (a, b, c) in s:
		s = abs((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) / 2
		if s > mx:
			mx = s
			ret = []
		if s == mx:
			ret.append([list(a), list(b), list(c)])
		if s > 0:
			i += 1
		j += 1
	if len(ret) <= 1:
		ret = ret[0]
	return [len(listPoints), j, i, ret, mx]


import math

def area(x, y, z):
	a = math.hypot(x[0] - y[0], x[1] - y[1])
	b = math.hypot(x[0] - z[0], x[1] - z[1])
	c = math.hypot(z[0] - y[0], z[1] - y[1])
	p = (a + b + c) / 2
	s = (p * (p - a) * (p - b) * (p - c)) ** 0.5
	if abs(s) / (a + b + c) < 1e-06:
		return 0
	return round(s, 6)

def find_biggTriang(listPoints):
	num_of_pts = len(listPoints)
	num_of_tri = 0
	best_area = None
	best_list = []
	for i in range(num_of_pts - 2):
		for j in range(i + 1, num_of_pts - 1):
			for k in range(j + 1, num_of_pts):
				a = area(listPoints[i], listPoints[j], listPoints[k])
				if a > 0:
					num_of_tri += 1
					if best_area is None or best_area < a:
						best_area = a
						best_list = []
					if a == best_area:
						best_list.append([list(listPoints[x]) for x in (i, j, k)])
	if len(best_list) == 1:
		best_list = best_list[0]
	return [num_of_pts, num_of_pts * (num_of_pts - 1) * (num_of_pts - 2) // 6, num_of_tri, best_list, best_area]


def find_biggTriang(P, m=0, c=0):
	(Z, V, l) = ([], set(), len(P))
	for i in range(l - 2):
		for j in range(i + 1, l - 1):
			for k in range(j + 1, l):
				((x, y), (u, v), (p, q)) = (P[i], P[j], P[k])
				s = abs((u - x) * (q - y) - (v - y) * (p - x)) / 2
				if s:
					V.add((i, j, k))
				T = [[x, y], [u, v], [p, q]]
				if m < s:
					(Z, m) = ([T], s)
				elif m == s:
					Z += [T]
				c += 1
	return [l, c, len(V), 1 < len(Z) and Z or Z[0], m]