The 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, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Croc Champ 2013 - Round 2 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only 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.

geometry

math

probabilities

two pointers

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/17/2024 21:20:22 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|