26453번 - Underground's SUNDAY 스페셜 저지다국어

문제

JAG Kingdom is a dimly lit country located underground. Sunlight doesn't usually reach JAG Kingdom, but there is one day every few years when sunlight reaches it: SUNDAY. On that day, the sun passes directly above a single hole in the "ceiling" of JAG Kingdom, and the sun peeks out. Bob, the boy in JAG Kingdom, is wondering how much time he can see all of the sun through the hole on the next SUNDAY. Please help him.

The ceiling of the JAG Kingdom is represented by a two-dimensional plane. The sun is represented by a circle of radius $R,ドル and its center moves straight from $(-10^{100}, 0)$ to $(10^{100}, 0)$ by 1ドル$ per unit time. The hole is represented by a simple polygon in the two-dimensional plane. Your task is to find the total time that the circle is contained within the polygon. A circle is contained in a polygon if and only if any point inside or on the circumference of the circle is contained inside or on the circumference of the polygon.

입력

The input consists of a single test case of the following format.

$N$ $R$

$x_1$ $y_1$

$\vdots$

$x_N$ $y_N$

The first line contains two integers $N$ and $R$ (3ドル ≤ N ≤ 10^5,ドル 1ドル ≤ R ≤ 10^6$) separated by a space, which represent the number of vertices of the polygon and a radius of the circle. Each of the next $N$ lines contains two integers $x_i$ and $y_i$ ($-10^6 ≤ x_i, y_i ≤ 10^6$) separated by a space, which represent the $i$-th vertex of the polygon. The polygon is guaranteed to be simple. In other words, no two edges of the polygon intersect each other.

출력

Print the total time that the circle is contained within the polygon. The answer will be considered as correct if the values output have an absolute or relative error less than 10ドル^{-5}$.

제한

힌트