Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

You are given a strictly convex polygon with $N$ vertices (numbered $1$ through $N$). For each valid $i$, the coordinates of the $i$-th vertex are $(X_{i}, Y_{i})$. You may perform the following operation any number of times (including zero):
Consider a *parent polygon*. Initially, this is the polygon you are given.
Draw one of its *child polygons* ― a simple non-degenerate polygon such that each of its sides is a chord of the parent polygon (it cannot be a side of the parent polygon). The operation cannot be performed if the parent polygon does not have any child polygons.
The child polygon which you drew becomes the new parent polygon.

Your goal is to draw as many sides of polygons in total as possible (including the polygon given at the start). Find this maximum total number of sides.

------  Input ------
The first line of the input 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$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $X_{i}$ and $Y_{i}$.

------  Output ------
Print a single line containing one integer ― the maximum possible number of sides of polygons.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$3 ≤ N ≤ 10^{5}$
$|X_{i}|, |Y_{i}| ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $2 \cdot 10^{6}$

----- Sample Input 1 ------ 
2

4

-100 1

0 2

0 0

100 1

7

-4 0

-3 -2

-3 2

0 -4

2 -3

2 3

3 2
----- Sample Output 1 ------ 
4

10
----- explanation 1 ------ 
Example case 1: It is not possible to draw a child polygon.

Example case 2: We can draw a child polygon once, e.g. with vertices $(-3, -2)$, $(-3, 2)$ and $(3, 2)$. Even though there are several other ways to draw a child polygon, it can only be a triangle, so the total number of sides cannot exceed $7+3 = 10$.

Difficulty: MEDIUM
Tags: Geometry

Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(n):
		(a, b) = map(int, input().split())
	chord = n
	while n >= 6:
		n = n // 2
		chord = chord + n
	print(chord)


n = 100001
l = [i for i in range(n)]
for i in range(6, n):
	l[i] += l[i // 2]
for _ in range(int(input())):
	leng = int(input())
	for j in range(leng):
		ll = input()
	print(l[leng])


t = input()
for c in range(0, int(t)):
	n = int(input())
	for i in range(n):
		a = input()
	sum = n
	while n // 2 >= 3:
		n //= 2
		sum += n
	print(sum)


for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		a = input()
	sum = n
	while n // 2 >= 3:
		n //= 2
		sum += n
	print(sum)


for t in range(int(input())):
	s = int(input())
	c = s
	for i in range(s):
		(x, y) = map(int, input().split())
	while s > 5:
		s = s // 2
		c += s
	print(c)


for i in range(int(input())):
	n = int(input())
	p = [-1] * n
	res = n
	for j in range(len(p)):
		(x, y) = input().split()
		p[j] = (int(x), int(y))
	while n > 5:
		res += n // 2
		n = n // 2
	print(res)


for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		input()
	c = n
	while n >= 6:
		n = n // 2
		c += n
	print(c)


for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	c = n
	while n >= 6:
		n = n // 2
		c += n
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = []
	for __ in range(n):
		a = list(map(int, input().split()))
		l.append(a)
	c = 0
	while n >= 3:
		c += n
		n //= 2
	print(c)


tests = int(input())
for i in range(tests):
	num = int(input())
	coors = []
	for _ in range(num):
		arr = list(map(int, input().split()))
		coors.append(arr)
	ans = 0
	while num >= 3:
		ans += num
		num //= 2
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for j in range(n):
		(x, y) = map(int, input().split())
		l += [[x, y]]
	ans = n
	while n // 2 >= 3:
		ans += n // 2
		n = n // 2
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	chord = n
	while n >= 6:
		n = n // 2
		chord = chord + n
	print(chord)


t = int(input())
for i in range(t):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	s = n
	while n // 2 >= 3:
		n = n // 2
		s = s + n
	print(int(s))


def f(polygon, additional):
	if polygon >= 6:
		new = polygon // 2
		additional += new
		return f(new, additional)
	else:
		return additional
t = int(input())
for j in range(t):
	polygon = int(input())
	for i in range(polygon):
		a = input()
	print(f(polygon, polygon))


for t in range(int(input())):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	chord = n
	while n > 5:
		n = n // 2
		chord += n
	print(chord)


for _ in range(int(input())):
	N = int(input())
	for _ in range(N):
		input()
	K = 0
	while N >= 3:
		K += N
		N >>= 1
	print(K)


def side(n):
	if n < 3:
		return 0
	else:
		return n + side(n // 2)
t = int(input())
for i in range(t):
	n = int(input())
	for j in range(n):
		(x, y) = map(int, input().split())
	print(side(n))


t = int(input())
for _ in range(t):
	n = int(input())
	sum = n
	for i in range(n):
		(x, y) = map(int, input().split(' '))
	while n > 5:
		n = n // 2
		sum = sum + n
	print(sum)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		(x, y) = map(int, input().split())
		l.append([x, y])
	c = n
	while n > 5:
		n = n // 2
		c += n
	print(c)


T = int(input())
for _ in range(T):
	N = int(input())
	for i in range(N):
		(X, Y) = map(int, input().split(' '))
	sum1 = N
	while N > 5:
		N = N // 2
		sum1 += N
	print(sum1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for _ in range(n):
		(x, y) = map(int, input().split(' '))
		arr.append([x, y])
	ver = n
	sides = n
	while ver > 5:
		ver = ver // 2
		sides += ver
	print(sides)


a = int(input())
for i in range(a):
	s = 0
	n = int(input())
	for j in range(n):
		a = input()
	while n > 2:
		s += n
		n = n // 2
	print(s)


t = int(input())
while t:
	t -= 1
	n = int(input())
	sides = n
	lst = []
	while sides:
		sides -= 1
		(a, b) = [int(x) for x in input().split()]
		lst.extend([a, b])
	c = n
	m = n
	while m // 2 >= 3:
		m = m // 2
		c += m
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	for j in range(n):
		input()
	sides = n
	while n >= 6:
		n = int(n / 2)
		sides += n
	print(sides)


for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	a = n
	while True:
		if n <= 5:
			break
		n = n // 2
		a += n
	print(a)


x = int(input())
for _ in range(x):
	n = int(input())
	for i in range(n):
		_ = input()
	temp = 0
	while n > 5:
		temp += n
		n = n // 2
	temp += n
	print(temp)


for t in range(int(input())):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	q = n
	while n > 5:
		u = n // 2
		q += u
		n = u
	print(q)


try:
	for i in range(int(input())):
		n = int(input())
		for i in range(n):
			aslfkaslkjf = input()
		s = n
		while n > 5:
			s += n // 2
			n = n // 2
		print(s)
except:
	pass


a = int(input())
for _ in range(a):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	if n <= 5:
		print(n)
		continue
	count = n
	while 1:
		if n == 3:
			break
		elif n == 4:
			break
		elif n == 5:
			break
		count += n // 2
		n = n // 2
	print(count)


def main():
	tc = int(input())
	while tc > 0:
		n = int(input())
		for i in range(n):
			x = input().split()
		dp = [0] * (n + 1)
		for i in range(n + 1):
			if i < 3:
				dp[i] = 0
			elif i <= 5:
				dp[i] = i
			else:
				dp[i] = i + dp[i // 2]
		print(dp[n])
		tc -= 1
main()


def main():
	tc = int(input())
	while tc > 0:
		n = int(input())
		for i in range(n):
			x = input().split()
		ans = 0
		while n >= 3:
			ans += n
			n = n // 2
		print(ans)
		tc -= 1
main()


def func2(n):
	tsum = n
	while n // 2 >= 3:
		tsum += n // 2
		n = n // 2
	print(tsum)
	return
t = int(input())
for i in range(t):
	n = int(input())
	for j in range(n):
		x = input()
	func2(n)


for _ in range(int(input())):
	n = int(input())
	on = n
	coords = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		coords.append([x, y])
	sol = 0
	while True:
		n //= 2
		if n < 3:
			print(sol + on)
			break
		sol += n


for i in range(int(input())):
	n = int(input())
	ans = n
	l = []
	for i in range(n):
		r = list(map(int, input().split()))
		l.append(r)
	while n > 5:
		n = n // 2
		ans = ans + n
	print(ans)


n = int(input())
while n > 0:
	num = int(input())
	for i in range(num):
		(x, y) = map(int, input().split())
	ans = num
	while num > 5:
		num = num // 2
		ans = ans + num
	print(ans)
	n = n - 1


from math import floor
n = int(input())
while n > 0:
	num = int(input())
	for i in range(num):
		(x, y) = map(int, input().split())
	ans = num
	while num > 5:
		num = floor(num / 2)
		ans = ans + num
	print(ans)
	n = n - 1


from math import floor
t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	sum = n
	while n >= 6:
		sum += floor(n / 2)
		n = floor(n / 2)
	print(sum)


import math
for _ in range(int(input())):
	n = int(input())
	px = [0] * n
	py = [0] * n
	for i in range(n):
		(px[i], py[i]) = map(int, input().split())
	ans = n
	while n >= 6:
		n = math.floor(n / 2)
		ans += n
	print(ans)


def A(n):
	if n <= 5:
		return n
	else:
		return n + A(n // 2)
for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		(a, b) = input().split()
	print(A(n))


def getsum(n):
	if n <= 5:
		return n
	else:
		return n + getsum(n // 2)
for _ in range(int(input())):
	p = int(input())
	for i in range(p):
		(m, n) = input().split()
	print(getsum(p))


for _ in range(int(input())):
	n = int(input())
	for v in range(n):
		input()
	cv = n
	while cv > 5:
		cv //= 2
		n += cv
	print(n)


for _ in range(int(input())):
	n = int(input())
	for v in range(n):
		(x, y) = map(int, input().split())
	cv = n
	while cv > 5:
		cv //= 2
		n += cv
	print(n)


t = int(input())
while t:
	n = int(input())
	pts = [list(input().split()) for i in range(n)]
	if n > 5:
		e = n
		while n > 5:
			e += n // 2
			n //= 2
		print(e)
	else:
		print(n)
	t -= 1


def solve(n):
	if n <= 5:
		return n
	else:
		return n + solve(n // 2)
test = int(input())
for i in range(test):
	n = int(input())
	for i in range(n):
		(a, b) = input().split()
	print(solve(n))


T = int(input())
for i in range(T):
	n = int(input())
	for i in range(n):
		a = list(map(int, input().split()))
	sides = n
	while n >= 6:
		sides += n // 2
		n = n // 2
	print(sides)


test = int(input())
for _ in range(test):
	n = int(input())
	for i in range(n):
		a = list(map(int, input().split()))
	sides = n
	while n >= 6:
		sides += n // 2
		n = n // 2
	print(sides)


for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	ans = n
	while n > 5:
		n = n // 2
		ans = ans + n
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	ans = n
	while n > 5:
		n = math.floor(n / 2)
		ans = ans + n
	print(ans)


import math
for _ in range(int(input())):
	sides = int(input())
	for ii in range(sides):
		input()
	count = sides
	while sides > 5:
		sides = math.floor(sides / 2)
		count = count + sides
	print(count)


def main():
	t = int(input())
	for test in range(t):
		sides = int(input())
		for i in range(sides):
			input()
		total = sides
		while sides >= 6:
			sides = int(sides / 2)
			total += sides
		print(total)
main()


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
mxn = 100005
dp = [0] * mxn
for i in range(3, 6):
	dp[i] = i
for i in range(6, mxn):
	dp[i] = i + dp[i // 2]
for _ in range(int(input())):
	(n,) = get_ints()
	a = []
	for i in range(n):
		a.append(get_array())
	print(dp[n])


for _ in range(int(input())):
	p = int(input())
	for j in range(p):
		(x, y) = map(int, input().split())
	ans = p
	while p > 5:
		p = p // 2
		ans += p
	print(ans)


for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		input()
	ans = n
	while n > 5:
		n = n // 2
		ans += n
	print(ans)


try:
	t = int(input())
	k = []
	for i in range(0, t):
		n = int(input())
		op = []
		for i in range(0, n):
			op.append(list(map(int, input().split(' '))))
		jk = n
		while n >= 6:
			n //= 2
			jk += n
		print(jk)
except:
	pass


def fun(n):
	lst = [3, 4, 5]
	if n in lst:
		return n
	else:
		return n + fun(n // 2)
for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	print(fun(n))


def poly(n):
	ans = n
	while n // 2 > 2:
		n = n // 2
		ans += n
	return ans
for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		(a, b) = map(int, input().split())
	print(poly(n))


def poly(n):
	answer = n
	while n // 2 > 2:
		n = n // 2
		answer += n
	return answer
t = int(input())
for i in range(t):
	n = int(input())
	for i in range(n):
		(a, b) = map(int, input().split())
	print(poly(n))


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	X = []
	Y = []
	for i in range(N):
		(x, y) = [int(i) for i in input().split()]
		X.append(x)
		Y.append(y)
	s = 0
	while N >= 3:
		s += N
		N = N // 2
	ans.append(s)
for i in ans:
	print(i)


def answer():
	v = n
	e = n
	while v > 5:
		v //= 2
		e += v
	return e
for T in range(int(input())):
	n = int(input())
	a = [list(map(int, input().split())) for i in range(n)]
	print(answer())