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 N = 1e5, M = 2e6;
struct CPOINT {
  int x, y;
  int& operator[](int id) { return id == 1 ? x : y; }
  bool operator<(const CPOINT& Cb) const& {
    if (x == Cb.x) return y < Cb.y;
    return x < Cb.x;
  }
} pnt[N + 3];
double Tex(CPOINT Ca, CPOINT Cb) {
  return Ca.x == Cb.x ? (Ca.y > Cb.y ? -1e9 : 1e9)
                      : double(Ca.y - Cb.y) / (Ca.x - Cb.x);
}
struct SSTACK {
  int stk[N + 3], top;
  void Push(int Vv) { stk[++top] = Vv; }
  int Size() { return top; }
  void Pop() { stk[top--] = 0; }
  int Fir() { return stk[top]; }
  int Sec() { return stk[top - 1]; }
  int& operator[](int id) { return stk[id]; }
};
SSTACK Sup, Slow;
int n;
int Cn[M + 3];
long long Rcnt;
int GetLowY(CPOINT Ca, CPOINT Cb, int x) {
  if (x == Ca.x) {
    if (Cb.x == Ca.x) return max(Cb.y, Ca.y);
    return Ca.y;
  }
  int Rl = -1, Rr = 2e6 + 1;
  while (Rl + 1 < Rr) {
    int Rm = (Rl + Rr) >> 1;
    if (1ll * (Rm - Ca.y) * (Cb.x - Ca.x) <= 1ll * (Cb.y - Ca.y) * (x - Ca.x))
      Rl = Rm;
    else
      Rr = Rm;
  }
  return Rl;
}
int GetHigY(CPOINT Ca, CPOINT Cb, int x) {
  if (x == Ca.x) {
    if (Cb.x == Ca.x) return min(Cb.y, Ca.y);
    return Ca.y;
  }
  int Rl = -1, Rr = 2e6 + 1;
  while (Rl + 1 < Rr) {
    int Rm = (Rl + Rr) >> 1;
    if (1ll * (Rm - Ca.y) * (Cb.x - Ca.x) >= 1ll * (Cb.y - Ca.y) * (x - Ca.x))
      Rr = Rm;
    else
      Rl = Rm;
  }
  return Rr;
}
long double Solve() {
  sort(pnt + 1, pnt + 1 + n);
  while (Sup.Size()) Sup.Pop();
  while (Slow.Size()) Slow.Pop();
  Sup.Push(1);
  Sup.Push(2);
  Slow.Push(1);
  Slow.Push(2);
  for (int i = 3; i <= n; i++) {
    while (Sup.Size() >= 2 &&
           Tex(pnt[Sup.Sec()], pnt[Sup.Fir()]) <= Tex(pnt[Sup.Fir()], pnt[i]))
      Sup.Pop();
    Sup.Push(i);
    while (Slow.Size() >= 2 && Tex(pnt[Slow.Sec()], pnt[Slow.Fir()]) >=
                                   Tex(pnt[Slow.Fir()], pnt[i]))
      Slow.Pop();
    Slow.Push(i);
  }
  int Lef = pnt[Sup[1]][1], Rig = pnt[Sup.Fir()][1];
  memset(Cn, 0, sizeof Cn);
  long double totCn = 0, Rs = 0, totCni = 0, totCni2 = 0;
  int Vup = 2, Vlow = 2;
  Rcnt = 0;
  for (int i = Lef; i <= Rig; i++) {
    while (i > pnt[Sup[Vup]][1]) Vup++;
    while (i > pnt[Slow[Vlow]][1]) Vlow++;
    Cn[i] = GetLowY(pnt[Sup[Vup - 1]], pnt[Sup[Vup]], i) -
            GetHigY(pnt[Slow[Vlow - 1]], pnt[Slow[Vlow]], i) + 1;
    Rcnt += Cn[i];
    totCn += (long double)Cn[i];
    totCni += (long double)i * Cn[i];
    totCni2 += (long double)i * i * Cn[i];
  }
  Rs = (totCn * totCni2 - totCni * totCni);
  return Rs;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &pnt[i][1], &pnt[i][2]);
    pnt[i][1] += (int)1e6;
    pnt[i][2] += (int)1e6;
  }
  long double Vans = Solve();
  for (int i = 1; i <= n; i++) swap(pnt[i][1], pnt[i][2]);
  Vans += Solve();
  printf("%.10f\n", double(Vans / Rcnt / (Rcnt - 1)));
  return 0;
}