Framing Pictures

2000ms

1048576K

Description:

Life has been discovered on Venus! What is more, the life forms appear to be convex polygons. An international consortium is designing a probe to send to Venus to take pictures, but they need to estimate the bandwidth needed to send back pictures.

When the probe takes a picture of a life form and wishes to send it back to Earth, the bandwidth required is proportional to the area of the bounding box (in other words, the smallest axis-aligned rectangle that contains the life-form). The shape and size of the life forms are known, but the orientation relative to the camera is random. You must thus determine the expected (average) area of the bounding box across all orientations.

Input:

The input describes the shape of a life form as a convex polygon in two dimensions.

The first line of input contains an integer $$$n$$$ ($$$3 \le n \le 200\,000$$$) — the number of vertices. The remaining $$$n$$$ lines each contain two integers $$$x$$$ and $$$y$$$ ($$$-10^9 \le x, y \le 10^9$$$) — the coordinates of a vertex. The vertices are given in counterclockwise order, and no three vertices lie on a straight line.

Output:

Output a single line containing the expected area of the bounding box of the polygon. Your answer should have an absolute or relative error of at most $$$10^{-6}$$$.

Sample Input:

Sample Output:

163.661977237

Sample Input:

Sample Output:

365.666028588

Note:

The pictures show example life forms and various camera orientations.

$\text{[math]}$ $\text{[math]}$

Informação

Provedor Codeforces

Código CF1578F