Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are given a convex polygon with N vertices.

You have to find any ⌊N/10⌋ distinct points with integer coordinates that lie strictly inside the polygon, or determine that such a set of points doesn't exist.

Note: ⌊⌋ denotes the floor function, typically used in integer division.

------ 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 denoting the number of vertices of the polygon.
The following N lines describe the vertices of the polygon in anticlockwise order. Each of these lines contains two space-separated integers x and y denoting the coordinates of one vertex.

------ Output ------ 

For each test case, if a valid set of points doesn't exist, print a single line containing the integer -1. Otherwise, print ⌊N/10⌋ lines. Each of these lines should contain two space-separated integers denoting the coordinates of one point.

The coordinates of all points should be integers with absolute value not exceeding 10^{9}. If there are multiple solutions, you may print any one.

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

$1 ≤ T ≤ 10^{5}$
$10 ≤ N ≤ 10^{5}$
$sum of N over all test cases ≤ 5 · 10^{5}$
$|x|, |y| ≤ 10^{9}$
$no three vertices of the polygon will be collinear$

------ Subtasks ------ 

Subtask #1 (30 points): 1 ≤ T ≤ 100, 10 ≤
N ≤ 100

Subtask #2 (70 points): original constraints

------ Example ------ 

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

1
11
0 0
1 1
2 3
2 5
0 10
-2 10
-5 9
-8 7
-8 4
-6 1
-2 0

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

0 1

------ Explanation ------ 

Example case 1: The polygon is shown in the picture:

You are required to output exactly ⌊N/10⌋ = ⌊11/10⌋ = 1 point.

One possible point that you can output is (0, 1). You can also output (0, 2), (-1, 3) or (1, 3).

However, (0, 0) is a wrong answer, because this point lies on the border of the convex polygon.

If you output (-1, -1), that's also a wrong answer, because this point lies outside the convex polygon. You can't output (1.1, 1.5) either, because it doesn't have integer coordinates, though it lies strictly inside the polygon.

Source: codechef | Difficulty: HARD
Tags: Geometry

Graph algorithms

Graph traversal

Constructive algorithms


Solutions:
def side(point1, point2, point):
	return (point2[0] - point1[0]) * (point1[1] - point[1]) - (point2[1] - point1[1]) * (point1[0] - point[0])

def print_ans(ans):
	for point in ans:
		print(point[0], point[1])

def answer(A, n):
	req = int(n / 10)
	got = 0
	ans = []
	for i in range(n):
		point = A[i]
		point_before = A[(n + i - 1) % n]
		point_after = A[(i + 1) % n]
		P = [point[0] - 1, point[1]]
		if P not in ans:
			if side(point_before, point, P) < 0 and side(point, point_after, P) < 0:
				ans.append(P)
				got += 1
				if got == req:
					print_ans(ans)
					return
	if req != got:
		for i in range(n):
			point = A[i]
			point_before = A[(n + i - 1) % n]
			point_after = A[(i + 1) % n]
			P = [point[0] + 1, point[1]]
			if P not in ans:
				if side(point_before, point, P) < 0 and side(point, point_after, P) < 0:
					ans.append(P)
					got += 1
					if got == req:
						print_ans(ans)
						return
	print(-1)
t = int(input())
for _ in range(t):
	n = int(input())
	A = [[0, 0] for _ in range(n)]
	for i in range(n):
		A[i] = list(map(int, input().split()))
	answer(A, n)


import sys
sys.setrecursionlimit(50000)

def sub(p, q):
	x = p[0] - q[0]
	y = p[1] - q[1]
	return [x, y]

def scprod(p, q, r):
	(x1, y1) = (q[0] - p[0], q[1] - p[1])
	(x2, y2) = (r[0] - q[0], r[1] - q[1])
	return x1 * y2 - x2 * y1 > 0

def inside(c, eq):
	n = len(eq)
	if not scprod(eq[0], eq[1], c) or not scprod(eq[-1], eq[0], c):
		return False
	(low, high) = (1, n - 1)
	for i in range(11):
		mid = (high + low) // 2
		if scprod(eq[0], eq[mid], c):
			low = mid
		else:
			high = mid
	return scprod(eq[low], eq[low + 1], c)

def floodfillUtil(c, points, k, cor, d):
	if len(points) >= k:
		return
	if not inside(c, cor):
		return
	else:
		points.add(c)
		if d == 1:
			floodfillUtil((c[0], c[1] + 1), points, k, cor, 1)
		elif d == 2:
			floodfillUtil((c[0] + 1, c[1] + 1), points, k, cor, 2)
		elif d == 3:
			floodfillUtil((c[0] + 1, c[1]), points, k, cor, 3)
		elif d == 4:
			floodfillUtil((c[0] + 1, c[1] - 1), points, k, cor, 4)
		elif d == 5:
			floodfillUtil((c[0], c[1] - 1), points, k, cor, 5)
		elif d == 6:
			floodfillUtil((c[0] - 1, c[1] - 1), points, k, cor, 6)
		elif d == 7:
			floodfillUtil((c[0] - 1, c[1]), points, k, cor, 7)
		elif d == 8:
			floodfillUtil((c[0] - 1, c[1] + 1), points, k, cor, 8)

def floodfill(c, points, k, cor):
	floodfillUtil((c[0], c[1] + 1), points, k, cor, 1)
	floodfillUtil((c[0] + 1, c[1] + 1), points, k, cor, 2)
	floodfillUtil((c[0] + 1, c[1]), points, k, cor, 3)
	floodfillUtil((c[0] + 1, c[1] - 1), points, k, cor, 4)
	floodfillUtil((c[0], c[1] - 1), points, k, cor, 5)
	floodfillUtil((c[0] - 1, c[1] - 1), points, k, cor, 6)
	floodfillUtil((c[0] - 1, c[1]), points, k, cor, 7)
	floodfillUtil((c[0] - 1, c[1] + 1), points, k, cor, 8)
for _ in range(int(input())):
	n = int(input())
	cor = []
	xcor = []
	ycor = []
	for i in range(n):
		cordinate = list(map(int, input().split()))
		cor.append(cordinate)
		xcor.append(cordinate[0])
		ycor.append(cordinate[1])
	count = 0
	k = n // 10
	ans = []
	flag = 0
	points = set()
	count = 0
	for i in range(len(cor)):
		if count == k:
			break
		c = cor[i]
		floodfill((c[0], c[1]), points, k, cor)
	points = list(points)
	if len(points) < k:
		print(-1)
	else:
		for a in range(k):
			print(points[a][0], points[a][1])


def kuch_kar_raha_hai(a, b, c):
	return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def bata_point_kidhar_hai(l, p, b):
	a = 1
	if kuch_kar_raha_hai(l[0], l[a], l[b]) > 0:
		(a, b) = (b, a)
	if kuch_kar_raha_hai(l[0], l[a], p) >= 0 or kuch_kar_raha_hai(l[0], l[b], p) <= 0:
		return False
	while abs(a - b) > 1:
		c = (a + b) // 2
		if kuch_kar_raha_hai(l[0], l[c], p) > 0:
			b = c
		else:
			a = c
	return kuch_kar_raha_hai(l[a], l[b], p) < 0
t = int(input())
while t:
	n = int(input())
	l = [(a, b) for i in range(n) for (a, b) in [map(int, input().split())]]
	d = {}
	for i in l:
		if bata_point_kidhar_hai(l, (i[0] + 1, i[1]), n - 1):
			d[i[0] + 1, i[1]] = 1
		if len(d) == n // 10:
			break
		if bata_point_kidhar_hai(l, (i[0] - 1, i[1]), n - 1):
			d[i[0] - 1, i[1]] = 1
		if len(d) == n // 10:
			break
		if bata_point_kidhar_hai(l, (i[0], i[1] + 1), n - 1):
			d[i[0], i[1] + 1] = 1
		if len(d) == n // 10:
			break
		if bata_point_kidhar_hai(l, (i[0], i[1] - 1), n - 1):
			d[i[0], i[1] - 1] = 1
		if len(d) == n // 10:
			break
	for i in d:
		print(i[0], i[1])
	t -= 1


for _ in range(int(input())):
	n = int(input())
	(xmax, xmin, ymax, ymin) = (-1 << 32, 1 << 32, -1 << 32, 1 << 32)
	P = []
	for _ in range(n):
		(xi, yi) = [int(i) for i in input().split(' ')]
		P.append([xi, yi])
		(xmin, xmax, ymin, ymax) = (min(xi, xmin), max(xi, xmax), min(yi, ymin), max(yi, ymax))
	(maxx, minn, k) = (0, 0, n // 10)
	for i in range(n):
		if P[i][1] == ymin:
			minn = i
		if P[i][1] == ymax:
			maxx = i
	if minn < maxx:
		(up, down) = (P[minn:maxx + 1], P[maxx + 1:] + P[0:minn])
	else:
		(down, up) = (P[maxx:minn + 1], P[minn + 1:] + P[0:maxx])
	for i in range(len(up)):
		if up[i][1] != ymax and up[i][1] != ymin:
			print(up[i][0] - 1, up[i][1])
			k -= 1
		if k == 0:
			break
	if k > 0:
		for i in range(len(down)):
			if down[i][1] != ymax and down[i][1] != ymin:
				print(down[i][0] + 1, down[i][1])
				k -= 1
			if k == 0:
				break


from math import atan2

def square(x1, y1, x2, y2, x3, y3):
	return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

def check(first, second, k=1, axel=0):
	label = 1
	n = len(first)
	for i in range(k):
		(l, r) = (1, len(first) - 1)
		if atan2(first[r][1] - first[axel][1], first[r][0] - first[axel][0]) <= atan2(second[i][1] - first[axel][1], second[i][0] - first[axel][0]):
			label = 0
			break
		if atan2(first[l][1] - first[axel][1], first[l][0] - first[axel][0]) >= atan2(second[i][1] - first[axel][1], second[i][0] - first[axel][0]):
			label = 0
			break
		while r - l > 1:
			m = (r + l) // 2
			if atan2(first[m][1] - first[axel][1], first[m][0] - first[axel][0]) >= atan2(second[i][1] - first[axel][1], second[i][0] - first[axel][0]):
				r = m
			else:
				l = m
		if abs(square(first[axel][0], first[axel][1], first[r][0], first[r][1], first[l][0], first[l][1])) == abs(square(second[i][0], second[i][1], first[r][0], first[r][1], first[l][0], first[l][1])) + abs(square(first[axel][0], first[axel][1], second[i][0], second[i][1], first[l][0], first[l][1])) + abs(square(first[axel][0], first[axel][1], first[r][0], first[r][1], second[i][0], second[i][1])) and abs(square(second[i][0], second[i][1], first[r][0], first[r][1], first[l][0], first[l][1])):
			continue
		else:
			label = 0
	if label:
		return 1
	else:
		return 0
for _ in range(int(input())):
	a = int(input())
	p = []
	for i in range(a):
		p.append([int(i) for i in input().split()])
	x = []
	y = []
	for i in p:
		x.append(i[0])
		y.append(i[1])
	x1 = min(x)
	x2 = max(x)
	y1 = min(y)
	y2 = max(y)
	pre = a // 10
	points = set()
	points2 = set()
	for i in p:
		(xc, yc) = (i[0], i[1])
		for j in range(1, 10000):
			if check(p, [[xc + j, yc]]) == 1:
				points.add((xc + j, yc))
				if len(points) >= pre:
					break
			else:
				break
		for j in range(1, 10000):
			if check(p, [[xc - j, yc]]) == 1:
				points.add((xc - j, yc))
				if len(points) >= pre:
					break
			else:
				break
		if len(points) >= pre:
			break
	points = list(points)
	if len(points) == 0 or len(points) < pre or pre == 0:
		print(-1)
	else:
		for i in range(pre):
			print(points[i][0], points[i][1])