Read problem statements in [Bengali], [Russian], [Mandarin] and [Vietnamese] as well.

Hulk has a set of distinct points P in the 2D plane. His signature move is Hulk Smash. He performed Hulk Smash on the set P which caused the points to change, and so he obtained a new set of points P'.

More formally, Hulk Smash makes the new set P' in the following way:
Initially, let P' be empty.
For every P_{i} and P_{j} such that 1 ≤ i < j ≤ N , add the mid point of P_{i} and P_{j} to the set P' (only if it didn't exist in it already).

So, P' is the set of midpoints of line segments connecting pairs of distinct points of P.
Note that points from P do not necessarily have to be in P'. See the samples below for a graphical example.

Find the number of points of P' which lie on the [convex hull] of P'. A point is said to lie on the convex hull if the shape of the convex hull is changed when this point is removed.

------ Input Format ------ 

- The first line contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N, denoting the size of P.
- The next N lines contain two space-separated integers each, where the i-th line contains P_{i}.x,P_{i}.y denoting the x-coordinate and y-coordinate of the i-th point. 

------ Output Format ------ 

For each test case, print a single line containing one integer - the number of points of P' which lie on its convex hull.

------ Constraints ------ 

$1 ≤ T ≤ 20$
$3 ≤ N ≤ 2 \cdot 10^{5}$
$-5 \cdot 10^{8} ≤ P_{i}.x, P_{i}.y ≤ 5 \cdot 10^{8}$
- The convex hull of the input set $P$ has positive area
- Sum of $N$ over all tests cases does not exceed $2 \cdot 10^{5}$

------ subtasks ------ 

Subtask 1 (20 points):
Sum of $N$ over all test cases does not exceed $10^{3}$

Subtask 2 (80 points):
Original constraints

----- Sample Input 1 ------ 
2
7
1 7
-6 -5
1 -6
-6 7
-4 3
-2 6
-3 -6
4
1 8
1 4
1 0
5 4

----- Sample Output 1 ------ 
8
4

----- explanation 1 ------ 
- In the below images, the set of points $P$ is denoted by the color pink, the set of points $P'$ is denoted by the color green. The blue point is the origin.
- The below image represents the first test case
- 

- The below image represents the second test case
- 

Note that by our definition, points $(1, 4)$ and $(3, 4)$ are not considered to lie on the convex hull of $P'$, because removing one of them does not change the shape of the hull.

Source: codechef | Difficulty: VERY_HARD
Tags: Geometry

Sorting

Sweep line algorithms

Complete search

Data structures


Solutions:
import math
from sys import stdin
input = stdin.readline

class Point:
	__slots__ = ['x', 'y', 'polarAngle']

	def __init__(self, x, y):
		self.x = x
		self.y = y
		self.polarAngle = 0.0

	def setPolarAngle(self, other):
		self.polarAngle = math.atan2(self.y - other.y, self.x - other.x)

	def direction(self, a, b, c):
		area = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)
		if area < 0:
			return -1
		elif area > 0:
			return 1
		else:
			return 0

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y

	def __ne__(self, x):
		return self.x != other.x or self.y != other.y

	def __hash__(self):
		return hash((self.x, self.y))

	def __repr__(self):
		return 'Point(' + str(self.x) + ',' + str(self.y) + ',' + '{:.2f}'.format(self.polarAngle) + ')'

def convexhull(points):
	points = sorted(points, key=lambda point: (point.y, point.x))
	points[0].polarAngle = 0.0
	for point in points[1:]:
		point.setPolarAngle(points[0])
	points = sorted(points, key=lambda point: point.polarAngle)
	hull = []
	hull.append(points[0])
	hull.append(points[1])
	for i in range(2, len(points)):
		top = hull.pop()
		while hull and top.direction(hull[-1], top, points[i]) <= 0:
			top = hull.pop()
		hull.append(top)
		hull.append(points[i])
	return hull

def sameside(line1, line2, p1, p2):
	return ((line1.y - line2.y) * (p1.x - line1.x) + (line2.x - line1.x) * (p1.y - line1.y)) * ((line1.y - line2.y) * (p2.x - line1.x) + (line2.x - line1.x) * (p2.y - line1.y)) > 0

def getmidpoints(points, N):
	hull1 = convexhull(points)
	sethull1 = set(hull1)
	N1 = len(hull1)
	centerX = sum((point.x for point in hull1)) / N1
	centerY = sum((point.y for point in hull1)) / N1
	center = Point(centerX, centerY)
	for i in range(N):
		if points[i] == center:
			points.pop(i)
			N -= 1
			break
	for point in points:
		point.setPolarAngle(center)
	points = sorted(points, key=lambda point: point.polarAngle)
	index_points = None
	for (i, point) in enumerate(points):
		if point in sethull1:
			index_points = i
			break
	index_hull1 = None
	for (i, point) in enumerate(hull1):
		if point == points[index_points]:
			index_hull1 = i
			break
	midpoints = set()
	for (i, point1) in enumerate(hull1):
		for point2 in [hull1[(i - 1) % N1], hull1[(i + 1) % N1]]:
			midpoints.add(Point(point1.x + point2.x, point1.y + point2.y))
	scope = [(index_hull1 - 1) % N1, index_hull1 % N1, (index_hull1 + 1) % N1]
	index_hull1_ini = index_hull1
	for twice in [1, 2]:
		index_hull1 = index_hull1_ini
		stop = 0
		for i in range(N):
			point1 = points[(index_points + i) % N]
			if point1 in sethull1:
				index_hull1 = (index_hull1 + 1) % N1
				scope.append((index_hull1 + 1) % N1)
				scope.pop(0)
				stop += 1
			else:
				for index2 in scope:
					point2 = hull1[index2]
					line1 = hull1[(index2 - 1) % N1]
					line2 = hull1[(index2 + 1) % N1]
					if sameside(line1, line2, point1, point2):
						midpoints.add(Point(point1.x + point2.x, point1.y + point2.y))
			if twice == 2 and stop > 2:
				break
	return midpoints

def solve(points, N):
	midpoints = getmidpoints(points, N)
	hull = convexhull(midpoints)
	return len(hull)
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	points = []
	for i in range(N):
		(x, y) = [int(x) for x in input().strip().split()]
		points.append(Point(x, y))
	print(solve(points, N))


import random
import sys
import math
mod = 10 ** 9 + 7
inf = float('inf')

def arrInt():
	return list(map(int, input().split()))

def ccw(o, a, b):
	return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def sortPoints(points):
	points.sort(key=lambda x: (x[1], x[0]))
	p = points[0]
	points.pop(0)
	points.sort(key=lambda i: (math.atan2(i[1] - p[1], i[0] - p[0]), i[1]))
	return p

def getMid(a, b):
	return [(a[0] + b[0]) / 2, (a[1] + b[1]) / 2]

def convexHull(points):
	p = sortPoints(points)
	points.append(p)
	stack = [p]
	for el in points:
		while len(stack) >= 2 and ccw(stack[-2], stack[-1], el) <= 0:
			stack.pop()
		stack.append(el)
	print(len(stack) - 1)

def solve(points):
	p = sortPoints(points)
	points.append(p)
	stack = [p]
	mid_points = []
	for i in range(len(points) - 1):
		mid_points.append(getMid(p, points[i]))
	for el in points:
		while len(stack) >= 2 and ccw(stack[-2], stack[-1], el) <= 0:
			mid_points.append(getMid(stack[-1], el))
			stack.pop()
		mid_points.append(getMid(stack[-1], el))
		stack.append(el)
	convexHull(mid_points)

def bruteForce(points):
	n = len(points)
	mid_points = []
	for i in range(n):
		for j in range(i + 1, n):
			mid_points.append(getMid(points[i], points[j]))
	p = sortPoints(points)
	points.append(p)
	stack = [p]
	for el in points:
		while len(stack) >= 2 and ccw(stack[-2], stack[-1], el) <= 0:
			stack.pop()
		stack.append(el)
	print('bruteforce', end=' ')
	convexHull(mid_points)
if 1 == 2:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	ip_points = [arrInt() for _ in range(n)]
	solve(ip_points)