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

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):
    """Builds a gradient description"""
    rise, tread = b[1] - a[1], b[0] - a[0]
    if rise == 0 or tread == 0:
        if rise == tread:
            return "p" # Single point
        elif rise == 0:
            return "y" # Y Axis constant
            # return "y={}".format(a[0])
        return "x" # X Axis constant
    else:
        # Warning: Float used in comparison later, could be a problem
        # but not likely given integer inputs
        return rise / tread

def collinear(a, b, c):
    """Determines if three points are colinear"""
    return grad(a, b) == grad(b, c)

def count_col_triang(input_):
    # Group the inputs based on colour, to unique points within each colour
    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))
    
    # Discard any colours with less than 3 unique points
    # Geometry fact: Need at least 3 points to form a triangle!
    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
        # Generate all possible trios of potential triangle vertices
        for a, b, c in combinations(point_list, 3):
            # Make sure the points are not collinear  
            if not collinear(a, b, c):
                # Yay! we found a triangle
                count += 1
        counts[color] = count
        total += count
    
    # Identify colours with greatest number of triangles
    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])
    
    # Collate stats and return
    return [len(input_), len(colors), total, most]


# determinant for this particular case
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_):
    # init variables
    colored = []
    colors = {}
    n_tri = []
    ncol = 0
    
    # separate points by colors
    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 each 3 points: calculate deteminant to determine if they form a triangle
    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
    
    # find maximum number of triangles
    tmax = max( n_tri )
    
    # find corresponding colors
    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]

    # get all with 3 or more points, kasi 3 points min sa triangle
    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

        # get the side lengths and compute area
        for vertices in comb_points:
            va, vb, vc = vertices
            # get sides using distance between 2 points formula
            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  # semi-perimeter
            area = (s*(s-a)*(s-b)*(s-c))**0.5

            # any 3 points with an area is a triangle
            if area != 0:
                triangle_count += 1
                color_triangle_count[color] += 1

    max_count = max(color_triangle_count.values())

    # get all colors with highest triangle count, append sa dulo count for format
    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_])) # cl is the full color-list
    
    d = {} # dictionary of color keys and triangle-count values
    for c in cl: # i[0] + [1] is a row of the test matrix: [xi, yi, 1]
        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) # maximally-triangled color
    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])))>1e-3)

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
#is_triangle = lambda a,b,c: __import__('numpy').linalg.det([(x,y,1) for x,y in (a,b,c)]) != 0 ## Precision issues

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 []]