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

Bear Limak loves preparing problems for algorithmic contests.
While his favorite part is inventing a story and writing the statement, he doesn't really like creating the test data.
Not only it's hard to do, but also making a mistake may spoil a problem completely, likely making a problem easier.

Limak prepared the following problem for you.
You start with an empty set of points on a two-dimensional plane.
There are N queries, each with one new point (x_{i}, y_{i}) to insert to the set.
After each query you must find the diameter of the set, i.e. the maximum distance between two points in the set.
To avoid printing floating numbers, after each query print the square of the diameter.

In many problems, in test generators an author should create some (possibly smart and tricky) data, and then shuffle it before printing.
Limak did the same in this problem, not noticing how crucial it may be.
You can assume that in every test the N points are randomly shuffled.
In other words, generators have a line "random_{shuffle}(array with points)" just before printing.
It isn't guaranteed that a problem is solvable within the time limit without this extra constraint.

------ Input ------ 

The first line of the input contains an integer N denoting the number of points.
The i-th of N following lines contains two space separated integers x_{i} and y_{i} denoting coordinates of the i-th point to insert. 

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

Output N lines.
The i-th line should contain the square of the diameter of the set with points (x_{1}, y_{1}), ..., (x_{i}, y_{i}).

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

$2 ≤ N ≤ 750,000$
$-10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}$
$Points are distinct.$
$Points are shuffled.$

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

$Subtask #1 (20 points) 2 ≤ N ≤ 1000$
$Subtask #2 (30 points) Points are generated uniformly at random.
In more detail: in each test file organizers chose two integers N and K,
after which a generator finds N distinct points with coordinates generated randomly from interval [-K, K].
All given original constraints are still satisfied.$
$Subtask #3 (50 points) original constraints$

----- Sample Input 1 ------ 
5

20 20

40 30

35 35

0 10

-170 1000000000
----- Sample Output 1 ------ 
0

500

500

2000

999999980000029000
----- explanation 1 ------ 

After the first query, the set contains only one point (20, 20). You should print 0 because there are no two points with positive distance between them.
After the second query, the set contains points (20, 20) and (40, 30).
The distance between them is sqrt((40-20)^2+(30-20)^2) = sqrt(500) so the squared distance is 500.
After the third query, the set is {(20,20), (40,30), (35,35)}.
The maximum distance is sqrt(500).
After the fourth query, the maximum distance is between (0,10) and (40,30).
Note that the given points may be collinear.
After the fifth query, the set contains all five points from the input.
Watch out for overflows because the answer may be very big, as you can see here.

Source: codechef | Difficulty: VERY_HARD
Tags: Geometry

Sweep line algorithms

Mathematics

Probability


Solutions:
import sys
from operator import itemgetter
N = int(input().strip())

def cross(p, q, r):
	return (p[0] - q[0]) * (r[1] - q[1]) - (p[1] - q[1]) * (r[0] - q[0])

def dist(p1, p2):
	return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
(U, L) = ([], [])

def Convex_hull(P):
	global U, L
	(U, L) = ([], [])
	sz = len(P)
	for i in range(sz):
		while len(U) >= 2 and cross(U[-2], U[-1], P[i]) <= 0:
			U.pop()
		while len(L) >= 2 and cross(L[-2], L[-1], P[i]) >= 0:
			L.pop()
		L.append(P[i])
		U.append(P[i])

def Find_maximization_pair():
	global U, L
	ans = 0
	(P, Q) = (0, 0)
	sizeU = len(U)
	sizeL = len(L)
	(i, j) = (0, sizeL - 1)
	while 0 < j or i < sizeU - 1:
		tmpdist = dist(U[i], L[j])
		if tmpdist > ans:
			(P, Q, ans) = (i, j, tmpdist)
		if i == sizeU - 1:
			j -= 1
		elif j == 0:
			i += 1
		elif (U[i + 1][1] - U[i][1]) * (L[j][0] - L[j - 1][0]) > (U[i + 1][0] - U[i][0]) * (L[j][1] - L[j - 1][1]):
			i += 1
		else:
			j -= 1
	return ([U[P][2], L[Q][2]], ans)

def log_out(count, value):
	s = str(value) + '\n'
	while count:
		if count % 2:
			sys.stdout.write(s)
		s += s
		count //= 2

def main():
	ans = []
	P = []
	for i in range(1, N + 1):
		s = sys.stdin.readline()
		(x, y) = map(int, s.strip().split())
		P.append((x, y, i))
	P.sort(key=itemgetter(0, 1))
	while len(P) > 1:
		size = len(P)
		Convex_hull(P)
		(res, disT) = Find_maximization_pair()
		maxx = max(res)
		count = size - maxx + 1
		ans.append((count, disT))
		P = list(filter(lambda it: it[2] < maxx, P))
	print(0)
	for it in reversed(ans):
		log_out(it[0], it[1])
main()