25100번 - E(length(CH)) 스페셜 저지다국어

You are given $n$ points on a plane. The i-th of them is activated with probability $p_i$, provided as part of the input. Find the expected circumference of the convex hull of all activated points.

The first line contains the number of points $n$ and the number $p^∗$. All points are activated with the probability $p_i = p^∗$, except for the first three, which are always activated ($p_1 = p_2 = p_3 = 1$); this way, the definition of the convex hull circumference is always sound. This is followed by $n$ lines, each containing space-separated coordinates of the $i$-th point, $x_i$, $y_i$.

Print out a single number — the expected circumference of the convex hull. Your result should differ by less than $0.001$ from the reference solution to be considered correct.

• $3 ≤ n ≤ 1000$; $0 ≤ p^∗ ≤ 1$
• $0 ≤ x_i , y_i ≤ 10\,000$; $x_i , y_i ∈ Z$
• No three points are colinear. No two points share an $x$ or $y$ coordinate.