Today, Chef has a fencing job at hand and has to fence up a surface covering N$N$ points. 
To minimize his work, he started looking for an algorithm that had him fence the least amount of length. 
He came up with the Convex Hull algorithm, but soon realized it gave him some random shape to fence. However, Chef likes rectangles and has a favourite number M$M$. 
Help him find the minimum perimeter he has to fence if he wants to fence a rectangle, with slope of one of the sides as M$M$, to cover all the points.

-----Input:-----
- The first line contains two integers N$N$ and M$M$, the number of points and the Chef's favourite Number.
- The next n lines contain two space separated integers X$X$ and Y$Y$, the coordinates of the point.

-----Output:-----
Print a single decimal number, denoting the perimeter of the rectangle. Answer will considered correct if it has absolute error less than 10−6$10^{-6}$.

-----Constraints-----
- 2≤N≤1000000$2 \leq N \leq 1000000$
- −1000≤M≤1000$-1000 \leq M \leq 1000$
- −1000000≤X≤1000000$-1000000 \leq X \leq 1000000$
- −1000000≤Y≤1000000$-1000000 \leq Y \leq 1000000$

-----Sample Input:-----
4 1
0 1
0 -1
1 0
-1 0

-----Sample Output:-----
5.656854249492380

-----Note:-----
- As the input size is large, it is recommended to use Fast IO.

Source: codechef | Difficulty: VERY_HARD
Tags: Geometry

Mathematics


Solutions:
import math
(n, m) = map(int, input().split())
hyp = math.sqrt(1 + m * m)
cosx = 1 / hyp
sinx = m / hyp
ptsx = []
ptsy = []
for i in range(n):
	(px, py) = list(map(int, input().strip().split()))
	ptsx.append(cosx * px + sinx * py)
	ptsy.append(cosx * py - sinx * px)
w = max(ptsx) - min(ptsx)
l = max(ptsy) - min(ptsy)
print(2 * l + 2 * w)


import math
(n, m) = map(int, input().split())
hyp = math.sqrt(1 + m * m)
cosx = 1 / hyp
sinx = m / hyp
pts = [[], []]
for i in range(n):
	p = input().split()
	px = int(p[0])
	py = int(p[1])
	pts[0].append(cosx * px + sinx * py)
	pts[1].append(cosx * py - sinx * px)
w = max(pts[0]) - min(pts[0])
l = max(pts[1]) - min(pts[1])
print(2 * l + 2 * w)


import math
import sys
(n, m) = map(int, input().split())
pts = [list(map(int, line.strip().split())) for line in sys.stdin]
hyp = math.sqrt(1 + m * m)
cosx = 1 / hyp
sinx = m / hyp
for apt in pts:
	(apt[0], apt[1]) = (cosx * apt[0] + sinx * apt[1], -sinx * apt[0] + cosx * apt[1])
l = max((a[0] for a in pts)) - min((a[0] for a in pts))
w = max((a[1] for a in pts)) - min((a[1] for a in pts))
print(2 * l + 2 * w)


import math
(n, m) = map(int, input().split())
pts = [list(map(int, input().strip().split())) for i in range(n)]
hyp = math.sqrt(1 + m * m)
cosx = 1 / hyp
sinx = m / hyp
for apt in pts:
	(apt[0], apt[1]) = (cosx * apt[0] + sinx * apt[1], -sinx * apt[0] + cosx * apt[1])
l = max((a[0] for a in pts)) - min((a[0] for a in pts))
w = max((a[1] for a in pts)) - min((a[1] for a in pts))
print(2 * l + 2 * w)


(n, m) = [int(x) for x in input().split()]
coordinates = []
for i in range(n):
	coordinates.append([int(y) for y in input().split()])
hyp = (1 + m * m) ** (1 / 2)
cosx = 1 / hyp
sinx = m / hyp
for point in coordinates:
	(point[0], point[1]) = (cosx * point[0] + sinx * point[1], -sinx * point[0] + cosx * point[1])
l = max((a[0] for a in coordinates)) - min((a[0] for a in coordinates))
b = max((a[1] for a in coordinates)) - min((a[1] for a in coordinates))
print(2 * (l + b))


import math
import numpy as np
(n, m) = map(int, input().split())
hyp = math.sqrt(1 + m * m)
cosx = 1 / hyp
sinx = m / hyp
px = np.empty(n)
py = np.empty(n)
for i in range(n):
	p = input().split()
	px[i] = int(p[0])
	py[i] = int(p[1])
w = max(cosx * px + sinx * py) - min(cosx * px + sinx * py)
l = max(cosx * py - sinx * px) - min(cosx * py - sinx * px)
print(2 * l + 2 * w)


import math
import numpy as np
(n, m) = map(int, input().split())
hyp = math.sqrt(1 + m * m)
cosx = 1 / hyp
sinx = m / hyp
pts = np.array([list(map(int, input().split())) for i in range(n)]).T
ptsx = cosx * pts[0] + sinx * pts[1]
ptsy = cosx * pts[1] - sinx * pts[0]
w = max(ptsx) - min(ptsx)
l = max(ptsy) - min(ptsy)
print(2 * l + 2 * w)


import math
(n, m) = map(int, input().split())
pts = [list(map(int, input().strip().split())) for i in range(n)]
hyp = math.sqrt(1 + m * m)
cosx = 1 / hyp
sinx = m / hyp
pts = [[cosx * p[0] + sinx * p[1], -sinx * p[0] + cosx * p[1]] for p in pts]
w = max(pts, key=lambda x: x[0])[0] - min(pts, key=lambda x: x[0])[0]
l = max(pts, key=lambda x: x[1])[1] - min(pts, key=lambda x: x[1])[1]
print(2 * l + 2 * w)


import math
(n, m) = map(int, input().split())
hyp = math.sqrt(1 + m * m)
cosx = 1 / hyp
sinx = m / hyp
for i in range(n):
	(px, py) = list(map(int, input().strip().split()))
	px_temp = cosx * px + sinx * py
	py_temp = cosx * py - sinx * px
	if i == 0:
		px_max = px_temp
		px_min = px_temp
		py_max = py_temp
		py_min = py_temp
	if px_temp > px_max:
		px_max = px_temp
	elif px_temp < px_min:
		px_min = px_temp
	if py_temp > py_max:
		py_max = py_temp
	elif py_temp < py_min:
		py_min = py_temp
w = px_max - px_min
l = py_max - py_min
print(2 * l + 2 * w)


import math
(n, m) = map(int, input().split())
pts = [list(map(int, input().strip().split())) for i in range(n)]
hyp = math.sqrt(1 + m * m)
cosx = 1 / hyp
sinx = m / hyp
pts = dict([[cosx * p[0] + sinx * p[1], -sinx * p[0] + cosx * p[1]] for p in pts])
w = max(pts.keys()) - min(pts.keys())
l = max(pts.values()) - min(pts.values())
print(2 * l + 2 * w)


from math import sqrt
(N, M) = input().split()
(N, M) = (int(N), float(M))
if M == 0:
	n = 0
	while n < N:
		(xi, yi) = input().split()
		(xi, yi) = (float(xi), float(yi))
		if n == 0:
			c1_min = c1_max = xi
			c2_min = c2_max = yi
		else:
			if c1_min > xi:
				c1_min = xi
			elif c1_max < xi:
				c1_max = xi
			if c2_min > yi:
				c2_min = yi
			elif c2_max < yi:
				c2_max = yi
		n += 1
	perimeter = 2 * (c2_max - c2_min + c1_max - c1_min)
else:
	n = 0
	while n < N:
		(xi, yi) = input().split()
		(xi, yi) = (float(xi), float(yi))
		temp1 = yi - M * xi
		temp2 = yi + xi / M
		if n == 0:
			c1_min = c1_max = temp1
			c2_min = c2_max = temp2
		else:
			if c1_min > temp1:
				c1_min = temp1
			elif c1_max < temp1:
				c1_max = temp1
			if c2_min > temp2:
				c2_min = temp2
			elif c2_max < temp2:
				c2_max = temp2
		n += 1
	perimeter = 2 * ((c1_max - c1_min) / sqrt(1.0 + M * M) + (c2_max - c2_min) / sqrt(1.0 + 1.0 / (M * M)))
print(perimeter)


import math
(n, m) = map(int, input().split())
h = math.sqrt(1 + m * m)
c = 1 / h
s = m / h
p = [[], []]
for i in range(n):
	x = input().split()
	p1 = int(x[0])
	p2 = int(x[1])
	p[0].append(c * p1 + s * p2)
	p[1].append(c * p2 - s * p1)
w = max(p[0]) - min(p[0])
l = max(p[1]) - min(p[1])
print(2 * l + 2 * w)


import math
(n, m) = map(int, input().split())
hyp = math.sqrt(1 + m * m)
cosx = 1 / hyp
sinx = m / hyp
for i in range(n):
	p = list(map(int, input().strip().split()))
	px = cosx * p[0] + sinx * p[1]
	py = cosx * p[1] - sinx * p[0]
	if i == 0:
		left = px
		rght = px
		lowr = py
		uppr = py
	else:
		left = min(left, px)
		rght = max(rght, px)
		lowr = min(lowr, py)
		uppr = max(uppr, py)
w = rght - left
l = uppr - lowr
print(2 * l + 2 * w)