Convex Hull of Credit Cards

This problem involves computing the perimeter of the convex hull of a set of identical credit card shapes that are placed on a plane. Each credit card is a rounded rectangle with width \(w\), height \(h\) and with all four corners replaced by quarter circles of radius \(r\) that are tangent to both adjacent sides. In other words, if you take a rectangle of width \(w\) and height \(h\) and replace each corner with a quarter circle of radius \(r\), the perimeter of a single card becomes

\(P_{card} = 2w + 2h + 2r(\pi - 4)\).

You are given \(n\) credit cards (all having the same size and orientation, i.e. axis-aligned) by the coordinates of their centers. The union of these cards is a convex set whose boundary may contain both line segments and circular arcs. A known property of Minkowski sums is that the convex hull of the union of translations of a convex shape is equal to the Minkowski sum of the convex hull of the translation vectors (in this case, the card centers) and the shape itself. Therefore, the perimeter of the convex hull is

\(P = P_{CH} + P_{card}\),

where \(P_{CH}\) is the perimeter of the convex hull of the set of center points. Note that when \(n=1\), the convex hull of the single center is just a point and we treat its perimeter as \(0\) (so the answer is just \(P_{card}\)). For \(n=2\), the convex hull is the line segment joining the two points and its "perimeter" is defined as twice the distance between them.

inputFormat

The first line contains four numbers: an integer \(n\) (the number of credit cards), and three real numbers \(w\), \(h\) and \(r\) which denote the width, height, and the rounding radius of each credit card, respectively. It is guaranteed that \(0 < r \le \min(w, h)/2\).

The following \(n\) lines each contain two real numbers \(x\) and \(y\), representing the coordinates of the center of a credit card. All cards are axis-aligned.

outputFormat

Output a single real number: the perimeter of the convex hull of the union of the credit cards. The answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

1 10 5 1
0 0

28.283185307179586