Archaeologists find ruins of Ancient ACM Civilization, and they want to rebuild it.
The ruins form a closed path on an x-y plane, which has $n$ endpoints. The endpoints locate on $(x_1,y_1)$, $(x_2,y_2)$, $\ldots,(x_n,y_n)$ respectively. Endpoint $i$ and endpoint $i-1$ are adjacent for $1<i\leq n$, also endpoint $1$ and endpoint $n$ are adjacent. Distances between any two adjacent endpoints are positive integers.
To rebuild, they need to build one cylindrical pillar at each endpoint, the radius of the pillar of endpoint $i$ is $r_i$. All the pillars perpendicular to the x-y plane, and the corresponding endpoint is on the centerline of it. We call two pillars are adjacent if and only if two corresponding endpoints are adjacent. For any two adjacent pillars, one must be tangent externally to another, otherwise it will violate the aesthetics of Ancient ACM Civilization. If two pillars are not adjacent, then there are no constraints, even if they overlap each other.
Note that $r_i$ must not be less than $0$ since we cannot build a pillar with negative radius and pillars with zero radius are acceptable since those kind of pillars still exist in their neighbors.
You are given the coordinates of $n$ endpoints. Your task is to find $r_1,r_2,\ldots,r_n$ which makes sum of base area of all pillars as minimum as possible.
For example, if the endpoints are at $(0,0)$, $(11,0)$, $(27,12)$, $(5,12)$, we can choose ($r_1$, $r_2$, $r_3$, $r_4$)$=$($3.75$, $7.25$, $12.75$, $9.25$). The sum of base area equals to $3.75^2\pi+$$7.25^2\pi+12.75^2\pi+9.25^2\pi=988.816\ldots$. Note that we count the area of the overlapping parts multiple times.
If there are several possible to produce the minimum sum of base area, you may output any of them.