Find the diameter of a convex polygon g. In other words, find a pair of points that have maximum distance between them.

Constraints

* 3 ≤ n ≤ 80000
* -100 ≤ xi, yi ≤ 100
* No point in the g will occur more than once.

Input


n
x1 y1
x2 y2
:
xn yn


The first integer n is the number of points in g.

In the following lines, the coordinate of the i-th point pi is given by two real numbers xi and yi. The coordinates of points are given in the order of counter-clockwise visit of them. Each value is a real number with at most 6 digits after the decimal point.

Output

Print the diameter of g in a line. The output values should be in a decimal fraction with an error less than 0.000001.

Examples

Input

3
0.0 0.0
4.0 0.0
2.0 2.0


Output

4.00


Input

4
0.0 0.0
1.0 0.0
1.0 1.0
0.0 1.0


Output

1.414213562373

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import array
from fractions import Fraction
import functools
import itertools
import math
import os
import sys

def main():
	N = read_int()
	P = []
	for _ in range(N):
		(x, y) = [Fraction(s) for s in inp().split()]
		P.append(Vec(x, y))
	print(solve(N, P))

def lcm(a, b):
	return a * b // math.gcd(a, b)

def solve(N, P):
	factor = 1
	for p in P:
		factor = lcm(lcm(factor, p.x.denominator), p.y.denominator)
	F = [Vec(int(p.x * factor), int(p.y * factor)) for p in P]
	pi = 0
	pyx = (F[0].y, F[0].x)
	qi = 0
	qyx = pyx
	for (i, a) in enumerate(F):
		ayx = (a.y, a.x)
		if pyx > ayx:
			pi = i
			pyx = ayx
		if qyx < ayx:
			qi = i
			qyx = ayx
	p0i = pi
	q0i = qi
	best = (F[pi] - F[qi]).abs2()
	while True:
		p = F[pi]
		p1 = F[(pi + 1) % N]
		q = F[qi]
		q1 = F[(qi + 1) % N]
		if (p1 - p).cross(q1 - q) >= 0:
			qi = (qi + 1) % N
		else:
			pi = (pi + 1) % N
		best = max(best, (F[pi] - F[qi]).abs2())
		if pi == p0i and qi == q0i:
			break
	return math.sqrt(Fraction(best, factor * factor))

class Vec(object):

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

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

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

	def __mul__(self, scalar):
		return Vec(self.x * scalar, self.y * scalar)

	def __rmul__(self, scalar):
		return Vec(self.x * scalar, self.y * scalar)

	def __truediv__(self, scalar):
		return Vec(self.x / scalar, self.y / scalar)

	def __iadd__(self, other):
		self.x += other.x
		self.y += other.y
		return self

	def __isub__(self, other):
		self.x -= other.x
		self.y -= other.y
		return self

	def __imul__(self, scalar):
		self.x *= scalar
		self.y *= scalar
		return self

	def __idiv__(self, scalar):
		self.x /= scalar
		self.y /= scalar
		return self

	def __neg__(self):
		return Vec(-self.x, -self.y)

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

	def __ne__(self, other):
		return not self.__eq__(other)

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

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

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

	def abs2(self):
		return self.x * self.x + self.y * self.y

	def __abs__(self):
		return math.sqrt(float(self.abs2()))

	def __repr__(self):
		return '({}, {})'.format(self.x, self.y)
DEBUG = 'DEBUG' in os.environ

def inp():
	return sys.stdin.readline().rstrip()

def read_int():
	return int(inp())

def read_ints():
	return [int(e) for e in inp().split()]

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)
main()


from typing import List

def cross(a: complex, b: complex) -> float:
	return a.real * b.imag - a.imag * b.real

def distance(i: int, j: int, coordinates: List[complex]) -> float:
	return abs(coordinates[i] - coordinates[j])
n = int(input())
points = [tuple(map(float, input().split())) for _ in range(n)]
min_x_idx = min(range(n), key=lambda x: points[x])
max_x_idx = max(range(n), key=lambda x: points[x])
coordinates = [re + 1j * im for (re, im) in points]
coordinates.append(coordinates[0])
ans = distance(min_x_idx, max_x_idx, coordinates)
(i, j) = (min_x_idx, max_x_idx)
while True:
	if 0 <= cross(coordinates[i + 1] - coordinates[i], coordinates[j + 1] - coordinates[j]):
		j = (j + 1) % n
	else:
		i = (i + 1) % n
	ans = max(ans, distance(i, j, coordinates))
	if min_x_idx == i and max_x_idx == j:
		break
print(ans)


from operator import itemgetter
from math import sqrt

def distance(p0, p1):
	(x0, y0) = p0
	(x1, y1) = p1
	return sqrt((x1 - x0) ** 2 + (y1 - y0) ** 2)

def cross(p0, p1, p2, p3):
	(x0, y0) = p0
	(x1, y1) = p1
	(x2, y2) = p2
	(x3, y3) = p3
	return (x1 - x0) * (y3 - y2) - (x3 - x2) * (y1 - y0)

def rotating_calipers(ps):
	ps.sort(key=itemgetter(0, 1))
	upper = []
	lower = []
	for p in ps:
		while len(upper) > 1 and cross(upper[-2], upper[-1], upper[-1], p) <= 0:
			upper.pop()
		while len(lower) > 1 and cross(lower[-2], lower[-1], lower[-1], p) >= 0:
			lower.pop()
		upper.append(p)
		lower.append(p)
	(nu, nl) = (len(upper), len(lower))
	(i, j) = (0, nl - 1)
	dist = 0.0
	while i < nu and j >= 0:
		d = distance(upper[i], lower[j])
		if dist < d:
			dist = d
		if i == nu - 1:
			j -= 1
		elif j == 0:
			i += 1
		elif cross(upper[i], upper[i + 1], lower[j - 1], lower[j]) > 0:
			i += 1
		else:
			j -= 1
	return dist

def run():
	n = int(input())
	ps = []
	for _ in range(n):
		(x, y) = [float(f) for f in input().split()]
		ps.append((x, y))
	print('{:.10f}'.format(rotating_calipers(ps)))
run()


from sys import stdin
readline = stdin.readline

def cross(a, b):
	return a.real * b.imag - a.imag * b.real

def dot(a, b):
	return a.real * b.real + a.imag * b.imag

def diff(p, i):
	return p[(i + 1) % len(p)] - p[i]

def convex_diameter(p):
	js = ks = 0
	for i in range(1, len(p)):
		if p[i].imag > p[js].imag:
			js = i
		if p[i].imag < p[ks].imag:
			ks = i
	maxd = abs(p[js] - p[ks])
	(j, k) = (js, ks)
	while True:
		if cross(diff(p, j), diff(p, k)) >= 0:
			k = (k + 1) % len(p)
		else:
			j = (j + 1) % len(p)
		if maxd < abs(p[j] - p[k]):
			maxd = abs(p[j] - p[k])
		if j == js and k == ks:
			break
	return maxd
n = int(readline())
p = [map(float, readline().split()) for _ in range(n)]
p = [x + y * 1j for (x, y) in p]
print('{:.6f}'.format(convex_diameter(p)))


import cmath
EPS = 1e-10

def OuterProduct(one, two):
	tmp = one.conjugate() * two
	return tmp.imag

def CCW(p, q, r):
	(one, two) = (q - p, r - q)
	if OuterProduct(one, two) > -EPS:
		return True
	else:
		return False

def ConvexDiameter(qs):
	n = len(qs)
	if n == 2:
		return abs(qs[0] - qs[1])
	(i, j) = (0, 0)
	for k in range(n):
		if qs[k].real < qs[i].real:
			i = k
		if qs[j].real < qs[k].real:
			j = k
	res = 0
	(si, sj) = (i, j)
	while i != sj or j != si:
		res = max(res, abs(qs[i] - qs[j]))
		if OuterProduct(qs[i - n + 1] - qs[i], qs[j - n + 1] - qs[j]) < -EPS:
			i = (i + 1) % n
		else:
			j = (j + 1) % n
	return res
n = int(input())
dots = []
for _ in range(n):
	(x, y) = map(float, input().split())
	dots.append(complex(x, y))
print('{:.12f}'.format(ConvexDiameter(dots)))


import cmath
import math
import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
PI = cmath.pi
TAU = cmath.pi * 2
EPS = 1e-08

class Point:
	CCW_COUNTER_CLOCKWISE = 1
	CCW_CLOCKWISE = -1
	CCW_ONLINE_BACK = 2
	CCW_ONLINE_FRONT = -2
	CCW_ON_SEGMENT = 0

	def __init__(self, c: complex):
		self.c = c

	@property
	def x(self):
		return self.c.real

	@property
	def y(self):
		return self.c.imag

	@staticmethod
	def from_rect(x: float, y: float):
		return Point(complex(x, y))

	@staticmethod
	def from_polar(r: float, phi: float):
		return Point(cmath.rect(r, phi))

	def __add__(self, p):
		return Point(self.c + p.c)

	def __iadd__(self, p):
		self.c += p.c
		return self

	def __sub__(self, p):
		return Point(self.c - p.c)

	def __isub__(self, p):
		self.c -= p.c
		return self

	def __mul__(self, f: float):
		return Point(self.c * f)

	def __imul__(self, f: float):
		self.c *= f
		return self

	def __truediv__(self, f: float):
		return Point(self.c / f)

	def __itruediv__(self, f: float):
		self.c /= f
		return self

	def __repr__(self):
		return '({}, {})'.format(round(self.x, 10), round(self.y, 10))

	def __neg__(self):
		return Point(-self.c)

	def __eq__(self, p):
		return abs(self.c - p.c) < EPS

	def __abs__(self):
		return abs(self.c)

	@staticmethod
	def ccw(a, b, c):
		b = b - a
		c = c - a
		det = b.det(c)
		if det > EPS:
			return Point.CCW_COUNTER_CLOCKWISE
		if det < -EPS:
			return Point.CCW_CLOCKWISE
		if b.dot(c) < -EPS:
			return Point.CCW_ONLINE_BACK
		if c.norm() - b.norm() > EPS:
			return Point.CCW_ONLINE_FRONT
		return Point.CCW_ON_SEGMENT

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

	def det(self, p):
		return self.x * p.y - self.y * p.x

	def dist(self, p):
		return abs(self.c - p.c)

	def norm(self):
		return abs(self.c)

	def phase(self):
		return cmath.phase(self.c)

	def angle(self, p, q):
		return (cmath.phase(q.c - self.c) - cmath.phase(p.c - self.c) + PI) % TAU - PI

	def area(self, p, q):
		return abs((p - self).det(q - self) / 2)

	def projection_point(self, p, q, allow_outer=False):
		diff_q = q - p
		r = (self - p).dot(diff_q) / abs(diff_q)
		phase = diff_q.phase()
		ret = Point.from_polar(r, phase) + p
		if allow_outer or (p - ret).dot(q - ret) < EPS:
			return ret
		return None

	def reflection_point(self, p, q):
		r = abs(self - p)
		angle = p.angle(q, self)
		angle = (q - p).phase() - angle
		return Point.from_polar(r, angle) + p

	def on_segment(self, p, q, allow_side=True):
		if not allow_side and (self == p or self == q):
			return False
		return abs((p - self).det(q - self)) < EPS and (p - self).dot(q - self) < EPS

class Line:

	def __init__(self, a: float, b: float, c: float):
		self.a = a
		self.b = b
		self.c = c

	@staticmethod
	def from_gradient(grad: float, intercept: float):
		return Line(grad, -1, intercept)

	@staticmethod
	def from_segment(p1, p2):
		a = p2.y - p1.y
		b = p1.x - p2.x
		c = p2.y * (p2.x - p1.x) - p2.x * (p2.y - p1.y)
		return Line(a, b, c)

	@property
	def gradient(self):
		return INF if self.b == 0 else -self.a / self.b

	@property
	def intercept(self):
		return INF if self.b == 0 else -self.c / self.b

	def is_parallel_to(self, l):
		return abs(Point.from_rect(self.a, self.b).det(Point.from_rect(l.a, l.b))) < EPS

	def is_orthogonal_to(self, l):
		return abs(Point.from_rect(self.a, self.b).dot(Point.from_rect(l.a, l.b))) < EPS

	def intersection_point(self, l):
		(a1, b1, c1) = (self.a, self.b, self.c)
		(a2, b2, c2) = (l.a, l.b, l.c)
		det = a1 * b2 - a2 * b1
		if abs(det) < EPS:
			return None
		x = (b1 * c2 - b2 * c1) / det
		y = (a2 * c1 - a1 * c2) / det
		return Point.from_rect(x, y)

class Segment:

	def __init__(self, p1, p2):
		self.p1 = p1
		self.p2 = p2

	def norm(self):
		return abs(self.p1 - self.p2)

	def intersects_with(self, s, allow_side=True):
		l1 = Line.from_segment(self.p1, self.p2)
		l2 = Line.from_segment(s.p1, s.p2)
		if l1.is_parallel_to(l2):
			return s.p1.on_segment(self.p1, self.p2, allow_side) or s.p2.on_segment(self.p1, self.p2, allow_side) or self.p1.on_segment(s.p1, s.p2, allow_side) or self.p2.on_segment(s.p1, s.p2, allow_side)
		else:
			p = l1.intersection_point(l2)
			return p.on_segment(self.p1, self.p2, allow_side) and p.on_segment(s.p1, s.p2, allow_side)

	def closest_point(self, p):
		d = (p - self.p1).dot(self.p2 - self.p1) / self.norm()
		if d < EPS:
			return self.p1
		if -EPS < d - self.norm():
			return self.p2
		return Point.from_polar(d, (self.p2 - self.p1).phase()) + self.p1

	def dist(self, p):
		return abs(p - self.closest_point(p))

	def dist_segment(self, s):
		if self.intersects_with(s):
			return 0.0
		return min(self.dist(s.p1), self.dist(s.p2), s.dist(self.p1), s.dist(self.p2))

	def has_point(self, p, allow_side=True):
		return p.on_segment(self.p1, self.p2, allow_side=allow_side)

class Polygon:

	def __init__(self, points):
		self.points = points

	def iter2(self):
		return zip(self.points, self.points[1:] + self.points[:1])

	def iter3(self):
		return zip(self.points, self.points[1:] + self.points[:1], self.points[2:] + self.points[:2])

	def area(self):
		dets = []
		for (p, q) in self.iter2():
			dets.append(p.det(q))
		return abs(math.fsum(dets)) / 2

	def is_convex(self, allow_straight=False, allow_collapsed=False):
		ccw = []
		for (a, b, c) in self.iter3():
			ccw.append(Point.ccw(a, b, c))
		ccw = set(ccw)
		if len(ccw) == 1:
			if ccw == {Point.CCW_CLOCKWISE}:
				return True
			if ccw == {Point.CCW_COUNTER_CLOCKWISE}:
				return True
		if allow_straight and len(ccw) == 2:
			if ccw == {Point.CCW_ONLINE_FRONT, Point.CCW_CLOCKWISE}:
				return True
			if ccw == {Point.CCW_ONLINE_FRONT, Point.CCW_COUNTER_CLOCKWISE}:
				return True
		if allow_collapsed and len(ccw) == 3:
			return ccw == {Point.CCW_ONLINE_FRONT, Point.CCW_ONLINE_BACK, Point.CCW_ON_SEGMENT}
		return False

	def has_point_on_edge(self, p):
		for (a, b) in self.iter2():
			if p.on_segment(a, b):
				return True
		return False

	def contains(self, p, allow_on_edge=True):
		angles = []
		for (a, b) in self.iter2():
			if p.on_segment(a, b):
				return allow_on_edge
			angles.append(p.angle(a, b))
		return abs(math.fsum(angles)) > EPS

	@staticmethod
	def convex_hull(points, allow_straight=False):
		points = points[:]
		points.sort(key=lambda p: (p.x, p.y))
		det_lower = -EPS if allow_straight else EPS
		sz = 0
		ret = [None] * (N * 2)
		for p in points:
			while sz > 1 and (ret[sz - 1] - ret[sz - 2]).det(p - ret[sz - 1]) < det_lower:
				sz -= 1
			ret[sz] = p
			sz += 1
		floor = sz
		for p in reversed(points[:-1]):
			while sz > floor and (ret[sz - 1] - ret[sz - 2]).det(p - ret[sz - 1]) < det_lower:
				sz -= 1
			ret[sz] = p
			sz += 1
		ret = ret[:sz - 1]
		if allow_straight and len(ret) > len(points):
			ret = points
		return ret

	@staticmethod
	def diameter(points):
		points = Polygon.convex_hull(points)
		if len(points) == 1:
			return 0.0
		if len(points) == 2:
			return abs(points[0] - points[1])
		si = points.index(min(points, key=lambda p: (p.x, p.y)))
		sj = points.index(max(points, key=lambda p: (p.x, p.y)))
		n = len(points)
		ret = 0.0
		(i, j) = (si, sj)
		while i != sj or j != si:
			ret = max(ret, abs(points[i] - points[j]))
			ni = (i + 1) % n
			nj = (j + 1) % n
			if (points[ni] - points[i]).det(points[nj] - points[j]) > 0:
				j = nj
			else:
				i = ni
		return ret
N = int(sys.stdin.buffer.readline())
XY = [list(map(float, sys.stdin.buffer.readline().split())) for _ in range(N)]
points = []
for (x, y) in XY:
	points.append(Point(complex(x, y)))
ans = Polygon.diameter(points)
print(ans)


def cross(p1, p2, q1, q2):
	p = p2 - p1
	q = q2 - q1
	return p.real * q.imag - p.imag * q.real
er = 1e-16

def convex_diameter(points, n):
	points.append(points[0])
	p0 = points[0]
	p1 = points[1]
	for (i, (q1, q2)) in enumerate(zip(points[1:], points[2:]), start=1):
		if cross(p0, p1, q1, q2) < -er:
			break
	max_d = abs(points[i] - points[0])
	points.append(points[1])
	side1 = zip(points[0:i + 1], points[1:i + 2])
	side2 = zip(points[i:n + 1], points[i + 1:])
	(p1, p2) = side1.__next__()
	(q1, q2) = side2.__next__()
	for i in range(n - 1):
		if cross(p1, p2, q1, q2) > er:
			(q1, q2) = side2.__next__()
		else:
			(p1, p2) = side1.__next__()
		max_d = max(max_d, abs(p1 - q1))
	return max_d

def string_to_complex(s):
	(x, y) = map(float, s.split())
	return x + y * 1j
import sys
file_input = sys.stdin
n = int(file_input.readline())
P = [string_to_complex(line) for line in file_input]
ans = convex_diameter(P, n)
print('{:f}'.format(ans))


def diff(i):
	(cp, np) = points[i:i + 2]
	return np - cp

def cross(a, b):
	return a.real * b.imag - a.imag * b.real

def diameter(i, j):
	return abs(points[i] - points[j])
n = int(input())
t_points = [tuple(map(float, input().split())) for _ in range(n)]
i = min(range(n), key=lambda x: t_points[x])
j = max(range(n), key=lambda x: t_points[x])
points = [re + 1j * im for (re, im) in t_points]
points.append(points[0])
tentative_diameter = diameter(i, j)
(it, jt) = (i, j)
while True:
	if cross(diff(it), diff(jt)) >= 0:
		jt = (jt + 1) % n
	else:
		it = (it + 1) % n
	tentative_diameter = max(tentative_diameter, diameter(it, jt))
	if it == i and jt == j:
		break
print(tentative_diameter)