You are given a convex polygon P with n distinct vertices p_1, p_2, ..., p_{n}. Vertex p_{i} has coordinates (x_{i}, y_{i}) in the 2D plane. These vertices are listed in clockwise order.

You can choose a real number D and move each vertex of the polygon a distance of at most D from their original positions.

Find the maximum value of D such that no matter how you move the vertices, the polygon does not intersect itself and stays convex.


-----Input-----

The first line has one integer n (4 ≤ n ≤ 1 000) — the number of vertices.

The next n lines contain the coordinates of the vertices. Line i contains two integers x_{i} and y_{i} ( - 10^9 ≤ x_{i}, y_{i} ≤ 10^9) — the coordinates of the i-th vertex. These points are guaranteed to be given in clockwise order, and will form a strictly convex polygon (in particular, no three consecutive points lie on the same straight line).


-----Output-----

Print one real number D, which is the maximum real number such that no matter how you move the vertices, the polygon stays convex.

Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}.

Namely, let's assume that your answer is a and the answer of the jury is b. The checker program will consider your answer correct if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


-----Examples-----
Input
4
0 0
0 1
1 1
1 0

Output
0.3535533906

Input
6
5 0
10 0
12 -4
10 -8
5 -8
3 -4

Output
1.0000000000



-----Note-----

Here is a picture of the first sample

[Image]

Here is an example of making the polygon non-convex.

[Image]

This is not an optimal solution, since the maximum distance we moved one point is  ≈ 0.4242640687, whereas we can make it non-convex by only moving each point a distance of at most  ≈ 0.3535533906.

Difficulty: MEDIUM_HARD
Tags: Geometry

Starter code:

Solutions:
def r(pred, cur, nxt):
	(x1, y1) = (nxt['x'] - pred['x'], nxt['y'] - pred['y'])
	(x2, y2) = (cur['x'] - pred['x'], cur['y'] - pred['y'])
	m = abs(x1 * y2 - x2 * y1)
	return m / (x1 ** 2 + y1 ** 2) ** 0.5
n = int(input())
a = []
for i in range(n):
	(x, y) = (int(_) for _ in input().split())
	a.append({'x': x, 'y': y})
min_r = r(a[-1], a[0], a[1]) / 2
for i in range(1, n):
	min_r = min(min_r, r(a[i - 1], a[i], a[(i + 1) % n]) / 2)
print(min_r)


from decimal import Decimal

def dist(a, b):
	(x1, y1) = a
	(x2, y2) = b
	return Decimal((x1 - x2) ** 2 + (y1 - y2) ** 2).sqrt()

def minh(a, b, c):
	m = dist(a, b)
	n = dist(b, c)
	k = dist(a, c)
	p = Decimal(m + n + k) / 2
	sqp = (p * (p - m) * (p - n) * (p - k)).sqrt()
	hm = Decimal(2) / m * sqp
	hn = Decimal(2) / n * sqp
	hk = Decimal(2) / k * sqp
	return min([hm, hn, hk])

def solve():
	n = int(input())
	coords = []
	for i in range(n):
		coords.append(tuple(map(int, input().split())))
	coords += coords
	res = min((minh(coords[i], coords[i + 1], coords[i + 2]) for i in range(n)))
	print(res / 2)
solve()


class Vector:

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

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

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

	def to(self, other):
		return other - self

	def __repr__(self):
		return '(%s %s)' % (self.x, self.y)

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

	def lensq(self):
		return self.x ** 2 + self.y ** 2
Vec = Vector

def getH(p, a, b):
	s2 = p.to(a).dot(p.to(b))
	return s2 / a.to(b).lensq() ** 0.5
pts = [Vec(*list(map(int, input().split()))) for i in range(int(input()))]
n = len(pts)
pts.append(pts[0])
pts.append(pts[1])
ans = 12351513153155135135
for i in range(n):
	ans = min(ans, getH(pts[i + 1], pts[i], pts[i + 2]) / 2)
print(ans)


n = int(input())
P = []

def h(p1, p2, m):
	return abs(((p2[0] - p1[0]) * (m[1] - p1[1]) - (p2[1] - p1[1]) * (m[0] - p1[0])) / ((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2) ** 0.5)
for i in range(n):
	P.append(list(map(int, input().split())))
answer = float('inf')
for i in range(n):
	cw = P[(i + 1) % n]
	ucw = P[i - 1]
	answer = min(answer, h(cw, ucw, P[i]) / 2)
print(answer)


from decimal import Decimal
n = int(input())
l = []
for i in range(n):
	(x, y) = map(int, input().split())
	l.append([x, y])
ans = 999999999999999
for i in range(n):
	x1 = l[i][0]
	y1 = l[i][1]
	x2 = l[(i + 1) % n][0]
	y2 = l[(i + 1) % n][1]
	x3 = l[(i + 2) % n][0]
	y3 = l[(i + 2) % n][1]
	a = Decimal((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)).sqrt()
	b = Decimal((x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3)).sqrt()
	c = Decimal((x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1)).sqrt()
	s = Decimal(a + b + c) / 2
	area = (s * (s - a) * (s - b) * (s - c)).sqrt()
	ans = min(ans, area / a, area / b, area / c)
print(ans)


from collections import Counter
n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
m = 10000000000
for i in range(-1, n - 1):
	b = a[i + 1][0] - a[i - 1][0]
	c = a[i - 1][1] - a[i + 1][1]
	d = -a[i - 1][1] * b - a[i - 1][0] * c
	m = min(m, ((a[i - 1][0] - a[i][0]) ** 2 + (a[i - 1][1] - a[i][1]) ** 2) ** 0.5, ((a[i + 1][0] - a[i][0]) ** 2 + (a[i + 1][1] - a[i][1]) ** 2) ** 0.5, abs(b * a[i][1] + c * a[i][0] + d) / (b ** 2 + c ** 2) ** 0.5)
print(m / 2)


import math

def dist(a, b, c):
	return abs((c[1] - a[1]) * b[0] - (c[0] - a[0]) * b[1] + c[0] * a[1] - c[1] * a[0]) / math.hypot(c[0] - a[0], c[1] - a[1])
N = int(input())
pts = [tuple(map(int, input().split())) for _ in range(N)]
MIN = 10000000000.0
for i in range(N - 2):
	MIN = min(MIN, dist(pts[i], pts[i + 1], pts[i + 2]))
MIN = min(MIN, dist(pts[N - 2], pts[N - 1], pts[0]))
MIN = min(MIN, dist(pts[N - 1], pts[0], pts[1]))
print(MIN / 2)


from math import hypot
n = int(input())

def square(a, b, c):
	first = [a[0] - c[0], a[1] - c[1]]
	second = [b[0] - c[0], b[1] - c[1]]
	return abs(first[0] * second[1] - first[1] * second[0])

def height(a, b, c):
	return square(a, b, c) / hypot(a[0] - b[0], a[1] - b[1])
points = []
for i in range(n):
	points.append(list(map(float, input().split())))
_max = 3000000000.0
for i in range(n):
	a = points[i]
	b = points[(i + 1) % n]
	c = points[(i + 2) % n]
	_max = min(_max, height(a, b, c) / 2)
	_max = min(_max, height(c, a, b) / 2)
	_max = min(_max, height(b, c, a) / 2)
print(_max)


from math import inf

def vect(x, y):
	return abs(sum([x[i] * (y[(i + 1) % 3] - y[(i + 2) % 3]) for i in range(3)]))

def l(x, y):
	return ((x[0] - x[2]) ** 2 + (y[0] - y[2]) ** 2) ** 0.5

def h(x, y):
	return vect(x, y) / l(x, y)
n = int(input())
x = []
y = []
for i in range(n):
	(a, b) = [int(x) for x in input().split()]
	x.append(a)
	y.append(b)
x += x[:2]
y += y[:2]
dmin = inf
for i in range(n):
	d = h(x[i:i + 3], y[i:i + 3]) / 2
	if dmin > d:
		dmin = d
print(dmin)


import math

class Pt:

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

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

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

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

	def len(self):
		return math.sqrt(self.x ** 2 + self.y ** 2)
n = int(input())
data = []
for i in range(n):
	data.append(Pt(*list(map(int, input().split()))))
min_ = 10 ** 10
for i in range(1, n - 1):
	A = data[i - 1]
	B = data[i + 1]
	C = data[i]
	r = abs(C - A ^ B - A) / (B - A).len()
	min_ = min(min_, r)
A = data[0]
B = data[n - 2]
C = data[n - 1]
r = abs(C - A ^ B - A) / (B - A).len()
min_ = min(min_, r)
A = data[1]
B = data[n - 1]
C = data[0]
r = abs(C - A ^ B - A) / (B - A).len()
min_ = min(min_, r)
print(min_ / 2)


import sys, queue, string, math
try:
	import dev_act_ffc429465ab634
	DEV = True
except:
	DEV = False

def log(*s):
	if DEV:
		print('LOG', *s)

class EJudge:

	def __init__(self, problem='default', reclim=1 << 30):
		self.problem = problem
		sys.setrecursionlimit(reclim)

	def use_files(self, infile='', outfile=''):
		if infile != '':
			self.infile = open(infile)
			sys.stdin = self.infile
		if infile != '':
			self.outfile = open(outfile, 'w')
			sys.stdout = self.outfile

	def use_bacs_files(self):
		self.use_files(self.problem + '.in', self.problem + '.out')

	def get_tl(self):
		while True:
			pass

	def get_ml(self):
		tmp = [[[5] * 100000 for _ in range(1000)]]
		while True:
			tmp.append([[5] * 100000 for _ in range(1000)])

	def get_re(self):
		s = (0,)[8]

	def get_wa(self, wstr='blablalblah'):
		for _ in range(3):
			print(wstr)
		exit()

class IntReader:

	def __init__(self):
		self.ost = queue.Queue()

	def get(self):
		return int(self.sget())

	def sget(self):
		if self.ost.empty():
			for el in input().split():
				self.ost.put(el)
		return self.ost.get()

	def release(self):
		res = []
		while not self.ost.empty():
			res.append(self.ost.get())
		return res

def tokenized(s):
	word = []
	for ch in s.strip():
		if ch == ' ':
			if word:
				yield ''.join(word)
				word = []
		elif 'a' <= ch <= 'z' or 'A' <= ch <= 'Z' or '0' <= ch <= '9':
			word.append(ch)
		else:
			if word:
				yield ''.join(word)
				word = []
			yield ch
	if word:
		yield ''.join(word)
		word = []
ej = EJudge()
int_reader = IntReader()
fmap = lambda f, *l: list(map(f, *l))
parse_int = lambda : fmap(int, input().split())

def dist(a, b):
	return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

def geron(la, lb, lc):
	halfp = (la + lb + lc) / 2
	return math.sqrt(halfp * (halfp - la) * (halfp - lb) * (halfp - lc))

def oriented(a, b, c):
	return abs((b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])) / 2

def add_tria_desec(a, b, c):
	global ans
	(la, lb, lc) = (dist(b, c), dist(c, a), dist(a, b))
	s = oriented(a, b, c)
	h = s * 2 / lb
	dmax = h / 2
	ans = min(ans, dmax)
n = int(input())
points = [parse_int() for _ in range(n)]
ans = 1 << 32
for idx in range(-2, n - 2):
	log(idx, idx + 1, idx + 2)
	add_tria_desec(points[idx], points[idx + 1], points[idx + 2])
print(ans)


import math

class Vector:

	@staticmethod
	def from_vectors(v1, v2):
		return Vector(v2.x - v1.x, v2.y - v1.y)

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

	def len(self):
		return math.sqrt(self.x ** 2 + self.y ** 2)

def cross_product(v1, v2):
	return v1.x * v2.y - v1.y * v2.x
n = int(input())
points = [Vector(*map(int, input().split())) for i in range(n)]
ans = float('inf')
for cur in range(n):
	prev = (cur - 1) % n
	nxt = (cur + 1) % n
	left = Vector.from_vectors(points[cur], points[prev])
	right = Vector.from_vectors(points[cur], points[nxt])
	base_len = Vector.from_vectors(points[prev], points[nxt]).len()
	area = abs(cross_product(left, right)) / 2
	ans = min(ans, area / base_len)
print(ans)


import math
from decimal import Decimal
n = int(input())
d = [[] for i in range(n)]
for i in range(n):
	d[i] = list(map(Decimal, input().split()))

def cnt(m):
	l = m - 1
	if l < 0:
		l = n - 1
	r = (m + 1) % n
	lol = Decimal(2)
	a = ((d[l][0] - d[m][0]) ** lol + (d[l][1] - d[m][1]) ** 2) ** Decimal(1 / 2)
	b = ((d[m][0] - d[r][0]) ** lol + (d[m][1] - d[r][1]) ** 2) ** Decimal(1 / 2)
	c = ((d[l][0] - d[r][0]) ** lol + (d[l][1] - d[r][1]) ** 2) ** Decimal(1 / 2)
	p = (a + b + c) / lol
	s = (p * (p - a) * (p - b) * (p - c)) ** Decimal(1 / 2)
	return Decimal(s / c)
ans = Decimal(cnt(0))
for i in range(0, n):
	ans = min(ans, cnt(i))
print(ans)


from sys import stdin, stdout
import math
n = int(stdin.readline().rstrip())
pointsList = []
for i in range(n):
	(x, y) = map(int, stdin.readline().rstrip().split())
	pointsList.append((x, y))
maxD = 999999999999999
for i in range(n):
	if i == n - 2:
		j = n - 1
		k = 0
	elif i == n - 1:
		j = 0
		k = 1
	else:
		j = i + 1
		k = i + 2
	(p1x, p1y) = pointsList[i]
	(p3x, p3y) = pointsList[k]
	p3x -= p1x
	p3y -= p1y
	theta = math.atan2(p3y, p3x)
	(p2x, p2y) = pointsList[j]
	p2x -= p1x
	p2y -= p1y
	y = -p2x * math.sin(theta) + p2y * math.cos(theta)
	maxD = min(y / 2, maxD)
print(maxD)


def calc(distance_1, distance_2, distance_3):
	return ((2 * distance_1 * distance_3 + 2 * distance_2 * distance_3 - distance_3 * distance_3 - (distance_1 - distance_2) ** 2) / (16 * distance_3)) ** 0.5

def distance(point_1, point_2):
	(point_1, y1) = point_1
	(point_2, y2) = point_2
	return (point_1 - point_2) ** 2 + (y1 - y2) ** 2
n = int(input().strip())
points = []
for _ in range(n):
	points.append(tuple([int(x) for x in input().strip().split()]))
min_ = float('inf')
for i in range(n):
	distance_1 = distance(points[i], points[(i + 1) % n])
	distance_2 = distance(points[(i + 2) % n], points[(i + 1) % n])
	distance_3 = distance(points[(i + 2) % n], points[i])
	min_ = min(min_, calc(distance_1, distance_2, distance_3))
print('%.9f' % min_)


from math import *
n = int(input())
r = [list(map(int, input().split())) for _ in range(n)]
ans = 10 ** 20
for i in range(n):
	(x0, y0) = r[(i + n - 1) % n]
	(x1, y1) = r[(i + 1) % n]
	(x, y) = r[i]
	ans = min(ans, abs((y1 - y0) * x - (x1 - x0) * y - (x0 * y1 - x1 * y0)) / sqrt((x1 - x0) ** 2 + (y1 - y0) ** 2))
print(ans / 2)


def calc(d1, d2, d3):
	return ((2 * d1 * d3 + 2 * d2 * d3 - d3 * d3 - (d1 - d2) ** 2) / (16 * d3)) ** 0.5

def dist(X1, X2):
	(x1, y1) = X1
	(x2, y2) = X2
	return (x1 - x2) ** 2 + (y1 - y2) ** 2
N = int(input().strip())
pts = []
for _ in range(N):
	pts.append(tuple([int(x) for x in input().strip().split()]))
minr = float('inf')
for i in range(N):
	d1 = dist(pts[i], pts[(i + 1) % N])
	d2 = dist(pts[(i + 2) % N], pts[(i + 1) % N])
	d3 = dist(pts[(i + 2) % N], pts[i])
	minr = min(minr, calc(d1, d2, d3))
print('%.9f' % minr)


from math import sqrt, hypot

def dist(a, b, c):
	return abs((c[1] - a[1]) * b[0] - (c[0] - a[0]) * b[1] + c[0] * a[1] - c[1] * a[0]) / hypot(c[0] - a[0], c[1] - a[1]) / 2
n = int(input())
liste = [list(map(int, input().split(' '))) for _ in range(n)]
d = -1
for i in range(n):
	if i == n - 1:
		(a, b, c) = (liste[n - 2], liste[n - 1], liste[0])
	else:
		(a, b, c) = (liste[i - 1], liste[i], liste[i + 1])
	if d != -1:
		d = min(d, dist(a, b, c))
	else:
		d = dist(a, b, c)
print(d)


import sys
import math
data = sys.stdin.read().split()
data_ptr = 0

def data_next():
	nonlocal data_ptr, data
	data_ptr += 1
	return data[data_ptr - 1]
N = int(data_next())
arr = list(zip(list(map(int, data[1::2])), list(map(int, data[2::2]))))

def cross(x1, y1, x2, y2):
	return x1 * y2 - x2 * y1

def dist(x, y):
	return math.sqrt(x * x + y * y)
ans = 4000000000.0
for i in range(N):
	(x1, y1) = arr[i - 1]
	(x2, y2) = arr[i]
	x1 -= arr[i - 2][0]
	x2 -= arr[i - 2][0]
	y1 -= arr[i - 2][1]
	y2 -= arr[i - 2][1]
	ans = min(ans, abs(cross(x1, y1, x2, y2) / dist(x2, y2) / 2))
print(ans)


def d(x, y, x1, y1, x2, y2):
	if x1 == x2:
		return abs(x - x1)
	elif y1 == y2:
		return abs(y - y1)
	else:
		return abs(((x - x1) / (x2 - x1) - (y - y1) / (y2 - y1)) / (1 / (x2 - x1) ** 2 + 1 / (y2 - y1) ** 2) ** 0.5)

def delta(a, b, c):
	return d(a[0], a[1], b[0], b[1], c[0], c[1]) / 2
n = int(input())
data = [list(map(int, input().split())) for t in range(n)]
data.append(data[0])
data.append(data[1])
print(min(map(delta, data[1:], data, data[2:])))


d = lambda i, j: (t[i][0] - t[j % n][0]) ** 2 + (t[i][1] - t[j % n][1]) ** 2
n = int(input())
t = [list(map(int, input().split())) for q in range(n)]
h = 1e+20
for i in range(n):
	(a, b, c) = (d(i - 1, i), d(i, i + 1), d(i - 1, i + 1))
	h = min(h, (4 * a * b - (a + b - c) ** 2) / c)
print(h ** 0.5 / 4)


import math

def dist(p1, p2):
	return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

def cross(p1, p2):
	return p1[0] * p2[1] - p1[1] * p2[0]

def parse_point(line):
	tokens = line.split()
	return (int(tokens[0]), int(tokens[1]))
n = int(input())
pt = [parse_point(input()) for _ in range(n)]
res = 1e+100
(pr1, pr2) = (None, None)
for i in range(len(pt)):
	pr1 = pt[i - 2]
	pr2 = pt[i - 1]
	cur = pt[i]
	p1 = (pr1[0] - pr2[0], pr1[1] - pr2[1])
	p2 = (cur[0] - pr2[0], cur[1] - pr2[1])
	c = dist(pr1, cur)
	if abs(cross(p1, p2) / 2) / c < res:
		res = abs(cross(p1, p2) / 2) / c
print(res)