Problem: Ksusha 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 ≤ 105) — 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 xi, yi (|xi|, |yi| ≤ 106) — 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1 << 17, MIL = 1 << 21;
int n;
pair<int, int> p[MAX];
int br[MIL];
int Norm(int x) { return (x + n) % n; }
long long Ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
  return (long long)a.first * (b.second - c.second) +
         (long long)b.first * (c.second - a.second) +
         (long long)c.first * (a.second - b.second);
}
inline long long SumBr(int x) { return (long long)x * (x + 1) / 2; }
inline long double SumKvad(int x) {
  return (long double)x * (x + 1) * (2 * x + 1) / 6;
}
inline long long Sq(long long x) { return x * x; }
long double Rijesi() {
  memset(br, 0, sizeof br);
  int najvisa = 0, najniza = 0;
  int lduz = 0, rduz = 0;
  for (int i = 1; i < n; i++) {
    if (p[i].second > p[najvisa].second) {
      najvisa = i;
      lduz = rduz = najvisa;
    } else if (p[i].second == p[najvisa].second) {
      if (p[i].first < p[lduz].first) lduz = i;
      if (p[i].first > p[rduz].first) rduz = i;
    }
    if (p[i].second < p[najniza].second) najniza = i;
  }
  int ltoc = 0, rtoc = MIL - 5;
  long long brtoc = 0;
  for (int vis = p[najvisa].second; vis >= p[najniza].second; vis--) {
    for (; vis < p[Norm(lduz + 1)].second; lduz = Norm(lduz + 1))
      ;
    for (; vis < p[Norm(rduz - 1)].second; rduz = Norm(rduz - 1))
      ;
    int pr = lduz, dr = Norm(lduz + 1);
    for (; ltoc - 1 >= min(p[pr].first, p[dr].first) &&
           Ccw(p[pr], p[dr], pair<int, int>(ltoc - 1, vis)) >= 0;
         ltoc--)
      ;
    for (; ltoc < min(p[pr].first, p[dr].first) ||
           Ccw(p[pr], p[dr], pair<int, int>(ltoc, vis)) < 0;
         ltoc++)
      ;
    pr = Norm(rduz - 1), dr = rduz;
    for (; rtoc + 1 <= max(p[pr].first, p[dr].first) &&
           Ccw(p[pr], p[dr], pair<int, int>(rtoc + 1, vis)) >= 0;
         rtoc++)
      ;
    for (; rtoc > max(p[pr].first, p[dr].first) ||
           Ccw(p[pr], p[dr], pair<int, int>(rtoc, vis)) < 0;
         rtoc--)
      ;
    br[vis] = max(0, rtoc - ltoc + 1);
    brtoc += br[vis];
  }
  long double koef = (long double)1 / ((long double)brtoc * (brtoc - 1) / 2);
  long double ret = 0;
  long double sumkvad = 0, sumlin = 0;
  long double broj = 0;
  for (int i = 0; i < MIL; i++) {
    ret += koef * br[i] * (Sq(i) * broj + sumkvad - 2 * sumlin * i);
    broj += br[i];
    sumlin += (long double)i * br[i];
    sumkvad += (long double)Sq(i) * br[i];
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &p[i].first, &p[i].second);
    p[i].first += MIL / 2;
    p[i].second += MIL / 2;
  }
  int rev = 0;
  for (int i = 0; i < n; i++)
    if (Ccw(p[i], p[Norm(i + 1)], p[Norm(i + 2)]) < 0) rev = 1;
  if (rev) reverse(p, p + n);
  long double rje = Rijesi();
  for (int i = 0; i < n; i++) swap(p[i].first, p[i].second);
  rev = 0;
  for (int i = 0; i < n; i++)
    if (Ccw(p[i], p[Norm(i + 1)], p[Norm(i + 2)]) < 0) rev = 1;
  if (rev) reverse(p, p + n);
  rje += Rijesi();
  printf("%.10lf\n", (double)rje / 2);
  return 0;
}