```if:java
___Note for Java users:___ Due to type checking in Java, inputs and outputs are formated quite differently in this language. See the footnotes of the description.


```

You have the following lattice points with their corresponding coordinates and each one with an specific colour.

 ```
Point   [x ,  y]     Colour
----------------------------
  A     [ 3,  4]     Blue
  B     [-7, -1]     Red
  C     [ 7, -6]     Yellow
  D     [ 2,  5]     Yellow
  E     [ 1, -5]     Red
  F     [-1,  4]     Red
  G     [ 1,  7]     Red
  H     [-3,  5]     Red
  I     [-3, -5]     Blue
  J     [ 4,  1]     Blue
```
We want to count the triangles that have the three vertices with the same colour. The following picture shows the distribution of the points in the plane with the required triangles.

![source: imgur.com](http://i.imgur.com/sP0l1i1.png)

The input that we will have for the field of lattice points described above is:

```
[[[3, -4], "blue"],  [[-7, -1], "red"], [[7, -6], "yellow"], [[2, 5], "yellow"],
 [[1, -5], "red"],   [[-1, 4], "red"],  [[1, 7], "red"],     [[-3, 5], "red"], 
 [[-3, -5], "blue"], [[4, 1], "blue"] ]
```
We see the following result from it:

```
Colour   Amount of Triangles       Triangles
Yellow         0                    -------
Blue           1                      AIJ
Red            10                   BEF,BEG,BEH,BFG,BFH,BGH,EFG,EFH,EHG,FGH
```
As we have 5 different points in red and each combination of 3 points that are not aligned.

We need a code that may give us the following information in order:

```
1) Total given points
2) Total number of colours
3) Total number of possible triangles
4) and 5) The colour (or colours, sorted alphabetically) with the highest amount of triangles
```

In Python our function will work like:

```
[10, 3, 11, ["red",10]]) == count_col_triang([[[3, -4], "blue"],  [[-7, -1], "red"], [[7, -6], "yellow"], [[2, 5], "yellow"], 
                                              [[1, -5], "red"],   [[-1, 4], "red"],  [[1, 7], "red"],     [[-3, 5], "red"],
                                              [[-3, -5], "blue"], [[4, 1], "blue"] ])
```
In the following case we have some points that are aligned and we have less triangles that can be formed:

```
[10, 3, 7, ["red", 6]] == count_col_triang([[[3, -4], "blue"],  [[-7, -1], "red"], [[7, -6], "yellow"], [[2, 5], "yellow"],
                                            [[1, -5], "red"],   [[1, 1], "red"],   [[1, 7], "red"],     [[1, 4], "red"], 
                                            [[-3, -5], "blue"], [[4, 1], "blue"] ])
```
Just to see the change with the previous case we have this:

![source: imgur.com](http://i.imgur.com/cCgO7ql.png)

In the special case that the list of points does not generate an even single triangle, the output will be like this case:

```
[9, 3, 0, []] == count_col_triang([[[1, -2], "red"], [[7, -6], "yellow"], [[2, 5], "yellow"], [[1, -5], "red"],
                                  [[1, 1], "red"],   [[1, 7], "red"],     [[1, 4], "red"],    [[-3, -5], "blue"], 
                                  [[4, 1], "blue"] ])
```
It will be this case:

![source: imgur.com](http://i.imgur.com/VB7t7Ij.png)

If in the result we have two or more colours with the same maximum amount of triangles, the last list should be like (e.g)

```
[35, 6, 35, ["blue", "red", "yellow", 23]]     # having the names of the colours sorted alphabetically
```
For the condition of three algined points A, B, C, you should know that the the following determinant should be 0.

```
 | xA    yA    1|
 | xB    yB    1|    = 0
 | xC    yC    1|

```
Assumptions:

- In the list you have unique points, so a point can have only one colour.

- All the inputs are valid

Enjoy it!

````if:java
---

___For java users:___

Two immutable objects, `ColouredPoint` and `TriangleResult`, have been designed for you in the preloaded part. You will receive inputs as lists of ColouredPoint objects and will return a TriangleResult object. For the last one, you may note the organization of the arguments of the constructor which differs a bit from the description above.

You may find below the signatures of the available methods of these objects:

````

Difficulty: MEDIUM_HARD
Tags: Fundamentals

Geometry

String algorithms

Mathematics

Data structures
Skill types: Data structures

Starter code:
def count_col_triang(a):
	

Solutions:
from itertools import combinations

def count_col_triang(a):
	(p, r) = ({}, {})
	for (xy, col) in a:
		p[col] = p.get(col, []) + [xy]
	for k in p:
		r[k] = sum((1 for c in combinations(p[k], 3) if triangle(*c)))
	mx = max(r.values())
	return [len(a), len(p), sum(r.values()), sorted((k for k in r if r[k] == mx)) + [mx] if mx else []]

def triangle(a, b, c):
	return area(*[((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** 0.5 for (p, q) in [(a, b), (a, c), (b, c)]]) > 0.0

def area(a, b, c):
	s = 0.5 * (a + b + c)
	return round(max(s * ((s - a) * (s - b) * (s - c)), 0.0) ** 0.5, 4)


from itertools import combinations

def grad(a, b):
	(rise, tread) = (b[1] - a[1], b[0] - a[0])
	if rise == 0 or tread == 0:
		if rise == tread:
			return 'p'
		elif rise == 0:
			return 'y'
		return 'x'
	else:
		return rise / tread

def collinear(a, b, c):
	return grad(a, b) == grad(b, c)

def count_col_triang(input_):
	colors = set(map(lambda t: t[1], input_))
	points = {col: set() for col in colors}
	for (coord, color) in input_:
		points[color].add(tuple(coord))
	points = {k: list(sorted(v)) for (k, v) in points.items() if len(v) > 2}
	total = 0
	counts = {}
	for (color, point_list) in points.items():
		count = 0
		for (a, b, c) in combinations(point_list, 3):
			if not collinear(a, b, c):
				count += 1
		counts[color] = count
		total += count
	most_count = max(counts.values())
	most = [c for (c, n) in counts.items() if n == most_count]
	most = [] if most_count == 0 else list(sorted(most)) + [most_count]
	return [len(input_), len(colors), total, most]


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

def count_col_triang(input_):
	colored = []
	colors = {}
	n_tri = []
	ncol = 0
	for (point, color) in input_:
		if color not in colors:
			colors[color] = ncol
			colored.append([])
			n_tri.append(0)
			ncol += 1
		colored[colors[color]].append(point)
	for (color, cpts) in enumerate(colored):
		if len(cpts) < 3:
			continue
		for k in range(len(cpts)):
			for l in range(k + 1):
				for m in range(l + 1):
					if det([cpts[k], cpts[l], cpts[m]]) != 0:
						n_tri[color] += 1
	tmax = max(n_tri)
	clrmax = []
	if tmax > 0:
		for color in sorted(colors):
			if n_tri[colors[color]] == tmax:
				clrmax.append(color)
		clrmax.append(tmax)
	return [len(input_), ncol, sum(n_tri), clrmax]


from collections import defaultdict
from itertools import combinations

def count_col_triang(points_colors):
	point_count = len(points_colors)
	colors = set((color for (points, color) in points_colors))
	color_count = len(colors)
	color_points = defaultdict(lambda : False)
	for c in colors:
		color_points[c] = [points for (points, color) in points_colors if color == c]
	color_points = defaultdict(lambda : False, ((color, points) for (color, points) in color_points.items() if len(points) >= 3))
	triangle_count = 0
	color_triangle_count = defaultdict(lambda : False)
	for (color, points) in color_points.items():
		comb_points = combinations(points, 3)
		color_triangle_count[color] = 0
		(x, y) = (0, 1)
		for vertices in comb_points:
			(va, vb, vc) = vertices
			a = ((vb[x] - va[x]) ** 2 + (vb[y] - va[y]) ** 2) ** 0.5
			b = ((vc[x] - vb[x]) ** 2 + (vc[y] - vb[y]) ** 2) ** 0.5
			c = ((va[x] - vc[x]) ** 2 + (va[y] - vc[y]) ** 2) ** 0.5
			s = (a + b + c) / 2
			area = (s * (s - a) * (s - b) * (s - c)) ** 0.5
			if area != 0:
				triangle_count += 1
				color_triangle_count[color] += 1
	max_count = max(color_triangle_count.values())
	colors_max_count = sorted([color for (color, count) in color_triangle_count.items() if count == max_count])
	colors_max_count.append(max_count)
	if max_count <= 0:
		colors_max_count = []
	return [point_count, color_count, triangle_count, colors_max_count]


from itertools import combinations as combos

def count_col_triang(in_):
	cl = list(set([i[1] for i in in_]))
	d = {}
	for c in cl:
		triples = combos([i[0] + [1] for i in in_ if i[1] == c], 3)
		test_matrices = list(map(list, triples))
		d[c] = len([i for i in test_matrices if determinant(i)])
	mc = max(d, key=d.get)
	maxcl = sorted([c for c in cl if d[c] and d[c] == d[mc]])
	sumtri = sum([d[i] for i in d])
	return [len(in_), len(cl), sumtri, maxcl + [d[mc]] if sumtri else []]

def determinant(m):
	(a, b, c, d, e, f, g, h, i) = tuple(m[0] + m[1] + m[2])
	return a * (e * i - f * h) - b * (d * i - f * g) + c * (d * h - e * g)


import numpy as np
from itertools import combinations

def ctri(lst):
	if len(lst) < 3:
		return 0
	return sum((1 for j in combinations(lst, 3) if abs(np.linalg.det(np.mat([i + [1] for i in j]))) > 0.001))

def count_col_triang(ipt):
	d = {}
	for i in ipt:
		if i[1] not in d:
			d[i[1]] = [i[0]]
		else:
			d[i[1]].append(i[0])
	p = {i: ctri(d[i]) for i in d}
	pmax = max(p.values())
	plst = [] if pmax == 0 else sorted([i for i in p if p[i] == pmax]) + [pmax]
	return [len(ipt), len(p), sum(p.values()), plst]


from itertools import combinations
from collections import defaultdict

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

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

def notOnSameLine(*pts):
	return bool(crossProd(vectorize(*pts[:2]), vectorize(*pts[1:])))

def count_col_triang(input_):
	dctPts = defaultdict(list)
	for (pos, color) in input_:
		dctPts[color].append(pos)
	dctTriangles = {color: sum((notOnSameLine(*threePts) for threePts in combinations(lst, 3))) for (color, lst) in dctPts.items()}
	maxTriangles = max(dctTriangles.values())
	return [len(input_), len(dctPts), sum(dctTriangles.values()), sorted((color for (color, n) in dctTriangles.items() if n == maxTriangles)) + [maxTriangles] if maxTriangles else []]


from itertools import combinations, groupby, starmap
is_triangle = lambda a, b, c: (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]) != 0
is_triangle = lambda a, b, c: a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]) != 0

def count_col_triang(input_):
	grouped = groupby(sorted(input_, key=lambda p: p[1]), key=lambda p: p[1])
	colored_triangles = {k: sum(starmap(is_triangle, combinations((p for (p, _) in g), 3))) for (k, g) in grouped}
	max_colored = max(colored_triangles.values())
	return [len(input_), len(colored_triangles), sum(colored_triangles.values()), sorted((c for (c, n) in colored_triangles.items() if n == max_colored)) + [max_colored] if max_colored else []]