Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Ksusha and Square

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKsusha is a vigorous mathematician. She is keen on absolutely incredible mathematical riddles.

Today Ksusha came across a convex polygon of non-zero area. She is now wondering: if she chooses a pair of distinct points uniformly among all integer points (points with integer coordinates) inside or on the border of the polygon and then draws a square with two opposite vertices lying in the chosen points, what will the expectation of this square's area be?

A pair of distinct points is chosen uniformly among all pairs of distinct points, located inside or on the border of the polygon. Pairs of points *p*, *q* (*p* ≠ *q*) and *q*, *p* are considered the same.

Help Ksusha! Count the required expectation.

Input

The first line contains integer *n* (3 ≤ *n* ≤ 10^{5}) — the number of vertices of Ksusha's convex polygon. Next *n* lines contain the coordinates of the polygon vertices in clockwise or counterclockwise order. The *i*-th line contains integers *x*_{i}, *y*_{i} (|*x*_{i}|, |*y*_{i}| ≤ 10^{6}) — the coordinates of the vertex that goes *i*-th in that order.

Output

Print a single real number — the required expected area.

The answer will be considered correct if its absolute and relative error doesn't exceed 10^{ - 6}.

Examples

Input

3

0 0

5 5

5 0

Output

4.6666666667

Input

4

-1 3

4 5

6 2

3 -5

Output

8.1583333333

Input

3

17 136

859 937

16 641

Output

66811.3704155169

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 06:26:30 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|