Chef has come to a 2 dimensional garden in which there are N points. Each point has coordinates (x, y), where x can either be 1 or 2 or 3. Chef will now choose every triplet of these N points and make a triangle from it. You need to tell the sum of areas of all the triangles the Chef makes.
Note that some of the triplets might not form proper triangles, and would end up as a line or a point (ie. degenerate), but that is fine because their area will be zero.

-----Input-----
- The first line contains a single integer T, the number of test cases. The description of each testcase follows.
- The first line of each test case contains an integer N denoting the number of points on the plane.
- The next N lines contain 2 space separated integers x and y denoting the coordinates of the points. 

-----Output-----
For each test case, output a single line containing the answer. Your answer will be considered correct if the absolute error is less than or equal to 10-2.

-----Constraints-----
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 2000
- 1 ≤ x ≤ 3
- 1 ≤ y ≤106
- All (x, y) pairs are distinct

-----Example-----
Input:
2
3
1 1
2 1
3 3
4
1 1
2 2
2 1
3 3

Output:
1.0
2.0

-----Explanation:-----
Test Case 1: There is only one triangle which has non-zero area, and it's area is 1, hence the output.
Test Case 2: Let the points be A(1,1), B(2,2), C(2,1), D(3,3). There are 3 non degenerate triangles possible. 

-  area ABC = 0.5
-  area BCD = 0.5
-  area ACD = 1
Total area = 2

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
# Author: Dancing Monkey | Created: 09.DEC.2018


import bisect
for _ in range(int(input())):
 n = int(input())
 x1 , x2, x3 = [], [], []
 for i in range(n):
  x, y = list(map(int, input().split()))

  if x == 1: x1.append(y)
  if x == 2: x2.append(y)
  if x == 3: x3.append(y)

 x1.sort()
 x2.sort()
 x3.sort()

 y1, y2, y3 = len(x1), len(x2), len(x3)
 area = 0
 for i in range(y1):
  for j in range(i+1, y1):
   area += abs(x1[i] - x1[j])*(y2 + (2*y3))

 for i in range(y3):
  for j in range(i+1, y3):
   area += abs(x3[i] - x3[j])*(y2 + (2*y1))

 for i in range(y2):
  for j in range(i+1, y2):
   area += abs(x2[i] - x2[j])*(y1 + y3)

 area /= 2

 s1 = [0]
 for i in range(y2): s1.append(s1[-1] + x2[i])
 # print(s1)
 s2 = [0]
 for i in range(y2):s2.append(s2[-1] + x2[y2 - 1 - i])
 # print(s2)

 for i in x1:
  for j in x3:
   p1 = (i + j) / 2
   p = bisect.bisect_left(x2, p1)
   # print('p', p)
   l = p
   h = y2 - l
   # print(l, h)

   area += p1*(l) - s1[l]
   # print('dfg', area)
   area += s2[h] - p1*(h)

 print(format(area, 'f'))
 # print()


# Author: Dancing Monkey | Created: 09.DEC.2018


import bisect
for _ in range(int(input())):
 n = int(input())
 x1 , x2, x3 = [], [], []
 for i in range(n):
  x, y = list(map(int, input().split()))

  if x == 1: x1.append(y)
  if x == 2: x2.append(y)
  if x == 3: x3.append(y)

 x1.sort()
 x2.sort()
 x3.sort()

 y1, y2, y3 = len(x1), len(x2), len(x3)
 area = 0
 for i in range(y1):
  for j in range(i+1, y1):
   area += abs(x1[i] - x1[j])*(y2 + (2*y3))

 for i in range(y3):
  for j in range(i+1, y3):
   area += abs(x3[i] - x3[j])*(y2 + (2*y1))

 for i in range(y2):
  for j in range(i+1, y2):
   area += abs(x2[i] - x2[j])*(y1 + y3)

 area /= 2

 s1 = [0]
 for i in range(y2): s1.append(s1[-1] + x2[i])
 # print(s1)
 s2 = [0]
 for i in range(y2):s2.append(s2[-1] + x2[y2 - 1 - i])
 # print(s2)

 for i in x1:
  for j in x3:
   p1 = (i + j) / 2
   p = bisect.bisect_left(x2, p1)
   # print('p', p)
   l = p
   h = y2 - l
   # print(l, h)

   area += p1*(l) - s1[l]
   # print('dfg', area)
   area += s2[h] - p1*(h)

 print(format(area, 'f'))
 # print()