Nezzar loves the game osu!.

osu! is played on beatmaps, which can be seen as an array consisting of distinct points on a plane. A beatmap is called nice if for any three consecutive points $A,B,C$ listed in order, the angle between these three points, centered at $B$, is strictly less than $90$ degrees.

Points $A,B,C$ on the left have angle less than $90$ degrees, so they can be three consecutive points of a nice beatmap; Points $A',B',C'$ on the right have angle greater or equal to $90$ degrees, so they cannot be three consecutive points of a nice beatmap.

Now Nezzar has a beatmap of $n$ distinct points $A_1,A_2,\ldots,A_n$. Nezzar would like to reorder these $n$ points so that the resulting beatmap is nice.

Formally, you are required to find a permutation $p_1,p_2,\ldots,p_n$ of integers from $1$ to $n$, such that beatmap $A_{p_1},A_{p_2},\ldots,A_{p_n}$ is nice. If it is impossible, you should determine it.


-----Input-----

The first line contains a single integer $n$ ($3 \le n \le 5000$).

Then $n$ lines follow, $i$-th of them contains two integers $x_i$, $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) — coordinates of point $A_i$.

It is guaranteed that all points are distinct.


-----Output-----

If there is no solution, print $-1$.

Otherwise, print $n$ integers, representing a valid permutation $p$.

If there are multiple possible answers, you can print any.


-----Examples-----

Input
5
0 0
5 0
4 2
2 1
3 0
Output
1 2 5 3 4


-----Note-----

Here is the illustration for the first test:

Please note that the angle between $A_1$, $A_2$ and $A_5$, centered at $A_2$, is treated as $0$ degrees. However, angle between $A_1$, $A_5$ and $A_2$, centered at $A_5$, is treated as $180$ degrees.

Difficulty: HARD
Tags: Constructive algorithms

Geometry

Sorting

Greedy algorithms

Mathematics
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
import sys
readline = sys.stdin.readline

def obt(i, j, k):
	(x1, y1) = (Points[i][0], Points[i][1])
	(x2, y2) = (Points[j][0], Points[j][1])
	(x3, y3) = (Points[k][0], Points[k][1])
	(X21, Y21) = (x1 - x2, y1 - y2)
	(X23, Y23) = (x3 - x2, y3 - y2)
	return X21 * X23 + Y21 * Y23 <= 0
N = int(readline())
Points = [tuple(map(int, readline().split())) for _ in range(N)]
L = [0, 1]
for i in range(2, N):
	L.append(i)
	if obt(L[i - 2], L[i - 1], L[i]):
		(L[i], L[i - 1]) = (L[i - 1], L[i])
	for j in range(i - 1, 1, -1):
		if obt(L[j - 2], L[j - 1], L[j]):
			(L[j - 1], L[j]) = (L[j], L[j - 1])
		else:
			break
print(*[i + 1 for i in L])


def solve(N, A):

	def check(a, b, c):
		(ax, ay) = a
		(bx, by) = b
		(cx, cy) = c
		return (bx - ax) * (cx - bx) + (by - ay) * (cy - by) < 0
	ans = [i for i in range(N)]
	for i in range(N - 2):
		for j in range(i, -1, -1):
			(a, b, c) = (ans[j], ans[j + 1], ans[j + 2])
			if not check(A[a], A[b], A[c]):
				(ans[j + 1], ans[j + 2]) = (ans[j + 2], ans[j + 1])
	return ans
n = int(input())
A = [tuple(map(int, input().split())) for i in range(n)]
ans = solve(n, A)
for i in range(n):
	ans[i] += 1
print(*ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	points = []
	for _ in range(n):
		points.append(list(map(int, input().split())))
	ans = [1]
	isCovered = [False] * n
	isCovered[0] = True
	curAns = 0
	for i in range(n - 1):
		maxDist = 0
		maxDistVertex = -1
		for j in range(n):
			if not isCovered[j] and (points[j][0] - points[curAns][0]) * (points[j][0] - points[curAns][0]) + (points[j][1] - points[curAns][1]) * (points[j][1] - points[curAns][1]) > maxDist:
				maxDist = (points[j][0] - points[curAns][0]) * (points[j][0] - points[curAns][0]) + (points[j][1] - points[curAns][1]) * (points[j][1] - points[curAns][1])
				maxDistVertex = j
		ans.append(maxDistVertex + 1)
		isCovered[maxDistVertex] = True
		curAns = maxDistVertex
	print(' '.join(map(str, ans)))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
n = int(input())
A = [0] + [tuple(map(int, input().split())) for i in range(n)]
ANS = [1, 2]

def judge(x, y, z):
	if (A[x][0] - A[y][0]) * (A[z][0] - A[y][0]) + (A[x][1] - A[y][1]) * (A[z][1] - A[y][1]) > 0:
		return 1
	else:
		return 0
for i in range(3, n + 1):
	if judge(i, ANS[-1], ANS[-2]) == 1:
		ANS.append(i)
		continue
	for j in range(1, len(ANS)):
		if judge(ANS[j - 1], i, ANS[j]) == 1:
			if j == 1 or judge(ANS[j - 2], ANS[j - 1], i) == 1:
				if j == len(ANS) - 1 or judge(i, ANS[j], ANS[j + 1]) == 1:
					ANS = ANS[:j] + [i] + ANS[j:]
					break
	else:
		print(pow(2, 10 ** 10 ** 9))
print(*ANS)


from math import sqrt
n = int(input())
points = [list(map(float, input().split())) for i in range(n)]
vis = [0] * n
order = [0]
vis[0] = 1
for i in range(n - 1):
	max_dist = 0
	best_points = [-1]
	for j in range(n):
		if not vis[j]:
			x = abs(points[j][0] - points[order[-1]][0])
			y = abs(points[j][1] - points[order[-1]][1])
			curr_dist_from_last = x ** 2 + y ** 2
			if max_dist == curr_dist_from_last:
				best_points.append(j)
			if max_dist < curr_dist_from_last:
				max_dist = curr_dist_from_last
				best_points = [j]
	max_dist = 0
	best_point = -1
	for j in best_points:
		x = int(abs(points[j][0] - points[order[-1]][0]))
		y = int(abs(points[j][1] - points[order[-1]][1]))
		curr_dist_from_last = x ** 2 + y ** 2
		if max_dist < curr_dist_from_last:
			max_dist = curr_dist_from_last
			best_point = j
	order.append(best_point)
	vis[best_point] = 1
for i in range(n):
	print(order[i] + 1)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N = int(input())
(X, Y) = ([0] * N, [0] * N)
for i in range(N):
	(X[i], Y[i]) = map(int, input().split())
lis = [False] * N
lis[0] = True
ans = [str(1)]
now = 0
for _ in range(N - 1):
	max_d = 0
	max_i = -1
	for i in range(N):
		if lis[i]:
			continue
		d = (X[i] - X[now]) * (X[i] - X[now]) + (Y[i] - Y[now]) * (Y[i] - Y[now])
		if d > max_d:
			max_d = d
			max_i = i
	lis[max_i] = True
	ans.append(str(max_i + 1))
	now = max_i
print(' '.join(ans))


from sys import stdin, stdout
from collections import defaultdict
import math

def main():
	n = int(stdin.readline())
	p = []
	for _ in range(n):
		(x, y) = list(map(int, stdin.readline().split()))
		p.append((x, y))
	ans = []
	for i in range(n):
		ans.append(i)
		for j in range(i, 1, -1):
			if (p[ans[j]][0] - p[ans[j - 1]][0]) * (p[ans[j - 1]][0] - p[ans[j - 2]][0]) + (p[ans[j]][1] - p[ans[j - 1]][1]) * (p[ans[j - 1]][1] - p[ans[j - 2]][1]) >= 0:
				(ans[j - 1], ans[j]) = (ans[j], ans[j - 1])
			else:
				break
	stdout.write(' '.join((str(x + 1) for x in ans)))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

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

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

def N():
	return int(input())

def S():
	return input().strip()

def print_list(l):
	print(' '.join(map(str, l)))
n = N()
p = set()
for i in range(1, n + 1):
	(x, y) = RL()
	p.add((x, y, i))
ans = []
(x, y, i) = p.pop()
ans.append(i)
for _ in range(n - 1):
	m = 0
	k = -1
	for (nx, ny, j) in p:
		d = (nx - x) * (nx - x) + (ny - y) * (ny - y)
		if d > m:
			m = d
			k = (nx, ny, j)
	(x, y) = (k[0], k[1])
	ans.append(k[2])
	p.discard(k)
print_list(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

class Vector:

	def __init__(self, x, y, id):
		self.x = x
		self.y = y
		self.id = id

	def __add__(self, other):
		return Vector(self.x + other.x, self.y + other.y, 0)

	def __sub__(self, other):
		return Vector(self.x - other.x, self.y - other.y, 0)

	def scale(self, n):
		return Vector(self.x * n, self.y * n)

	def dot(self, other):
		return self.x * other.x + self.y * other.y

	def cross(self, other):
		return self.x * other.y - other.x * self.y

	def mag2(self):
		return dot(self)

	def rot90(self):
		return Vector(-self.y, self.x)

	def rot270(self):
		return Vector(self.y, -self.x)

	def hashCode(self):
		return self.x << 13 ^ self.y * 57

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

	def __lt__(self, other):
		if self.x != other.x:
			return self.x < other.x
		return self.y < other.y
n = inp()
point = []
for i in range(n):
	(x, y) = invr()
	point.append(Vector(x, y, i + 1))
while 1:
	flag = True
	for i in range(n - 2):
		x = point[i]
		y = point[i + 1]
		z = point[i + 2]
		a = x - y
		b = z - y
		if a.dot(b) <= 0:
			(point[i + 1], point[i + 2]) = (point[i + 2], point[i + 1])
			flag = False
	if flag:
		break
for p in point:
	print(p.id, end=' ')


import sys, io, os
if os.environ['USERNAME'] == 'kissz':
	inp = open('in.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

	def debug(*args):
		pass
n = int(inp())
points = [(0, 0)] * (n + 1)
for i in range(1, n + 1):
	(x, y) = map(int, inp().split())
	points[i] = (x, y)
perm = list(range(1, n + 1))
while True:
	for i in range(n - 2):
		a = points[perm[i]]
		b = points[perm[i + 1]]
		c = points[perm[i + 2]]
		if (b[0] - a[0]) * (c[0] - b[0]) + (b[1] - a[1]) * (c[1] - b[1]) >= 0:
			(perm[i + 1], perm[i + 2]) = (perm[i + 2], perm[i + 1])
			break
	else:
		break
print(*perm)


n = int(input())
points = [list(map(int, input().split())) for i in range(n)]
pointsx = [points[i][0] for i in range(n)]
pointsy = [points[i][1] for i in range(n)]
vis = [0] * n
order = [0]
vis[0] = 1
for i in range(n - 1):
	max_dist = 0
	best_points = [-1]
	lastx = pointsx[order[-1]]
	lasty = pointsy[order[-1]]
	for j in range(n):
		if not vis[j]:
			curr_dist_from_last = (pointsx[j] - lastx) * (pointsx[j] - lastx) + (pointsy[j] - lasty) * (pointsy[j] - lasty)
			if max_dist < curr_dist_from_last:
				max_dist = curr_dist_from_last
				best_point = j
	order.append(best_point)
	vis[best_point] = 1
for i in range(n):
	print(order[i] + 1)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N = int(input())
points = []
for i in range(N):
	(x, y) = map(int, input().split())
	points.append(x)
	points.append(y)
lis = [0] * N
lis[0] = 1
ans = [str(1)]
now = 0
for _ in range(N - 1):
	max_d = 0
	max_i = -1
	for i in range(N):
		if lis[i]:
			continue
		d = (points[i * 2] - points[now * 2]) * (points[i * 2] - points[now * 2]) + (points[i * 2 + 1] - points[now * 2 + 1]) * (points[i * 2 + 1] - points[now * 2 + 1])
		if d > max_d:
			max_d = d
			max_i = i
	lis[max_i] = 1
	ans.append(str(max_i + 1))
	now = max_i
print(' '.join(ans))


import os, io, math
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
points = []
n = int(input())
visited = [0] * n
visited[0] = 1
for i in range(n):
	(x, y) = map(int, input().split())
	points.append(x)
	points.append(y)
ans = ['1']
currx = points[0]
curry = points[1]
for i in range(n - 1):
	maxdist = 0
	best = -1
	for j in range(n):
		if visited[j]:
			continue
		nextx = points[2 * j]
		nexty = points[2 * j + 1]
		dist = (nextx - currx) * (nextx - currx) + (nexty - curry) * (nexty - curry)
		if maxdist < dist:
			maxdist = dist
			best = j
	ans.append(str(best + 1))
	visited[best] = 1
	currx = points[2 * best]
	curry = points[2 * best + 1]
print(' '.join(ans))


class Node:

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

	def getDist(self, a):
		dx = a.x - self.x
		dy = a.y - self.y
		return dx * dx + dy * dy
n = int(input())
a = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(Node(x, y))
ans = [0]
vis = set()
vis.add(0)
while len(ans) < n:
	cur = ans[-1]
	maxDis = 0
	maxPos = 0
	for j in range(n):
		if cur == j or j in vis:
			continue
		val = a[cur].getDist(a[j])
		if val > maxDis:
			maxDis = val
			maxPos = j
	vis.add(maxPos)
	ans.append(maxPos)
for i in ans:
	print(i + 1, end=' ')
print()


import sys
input = sys.stdin.readline
from math import gcd

def main():
	n = int(input())
	points = [tuple(map(int, input().split())) for _ in range(n)]
	ans = [i for i in range(n)]

	def ng(i):
		(x1, y1) = points[ans[i - 1]]
		(x2, y2) = points[ans[i]]
		(x3, y3) = points[ans[i + 1]]
		(dx1, dy1) = (abs(x1 - x2), abs(y1 - y2))
		(dx2, dy2) = (abs(x2 - x3), abs(y2 - y3))
		(dx3, dy3) = (abs(x1 - x3), abs(y1 - y3))
		d1 = dx1 ** 2 + dy1 ** 2
		d2 = dx2 ** 2 + dy2 ** 2
		d3 = dx3 ** 2 + dy3 ** 2
		return d3 >= d1 + d2
	flg = True
	while flg:
		flg = False
		for i in range(1, n - 1):
			if ng(i):
				(ans[i], ans[i + 1]) = (ans[i + 1], ans[i])
				flg = True
	for i in range(n):
		ans[i] += 1
	print(*ans)
for _ in range(1):
	main()