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 = 100004, M = 2000004, P = 1000000;
struct rec {
  int x, y;
} p[N], u[N], d[N];
int n, nu, nd, ul, ur, dl, dr, ly[M], ry[M], cnt[M];
double ans = 0;
bool b[N];
long long cross(int p0, int p1, int p2) {
  return (long long)(p[p1].x - p[p0].x) * (p[p2].y - p[p0].y) -
         (long long)(p[p1].y - p[p0].y) * (p[p2].x - p[p0].x);
}
void process() {
  int i;
  nu = nd = 0;
  ul = ur = dl = dr = 1;
  for (i = 1; i <= n; i++) {
    if ((p[i].x < p[ul].x) || ((p[i].x == p[ul].x) && (p[i].y > p[ul].y)))
      ul = i;
    if ((p[i].x > p[ur].x) || ((p[i].x == p[ur].x) && (p[i].y > p[ur].y)))
      ur = i;
    if ((p[i].x < p[dl].x) || ((p[i].x == p[dl].x) && (p[i].y < p[dl].y)))
      dl = i;
    if ((p[i].x > p[dr].x) || ((p[i].x == p[dr].x) && (p[i].y < p[dr].y)))
      dr = i;
  }
  if (cross(1, 2, 3) > 0) {
    for (i = ul;; i = (i == 1) ? n : (i - 1)) {
      u[++nu] = p[i];
      if (i == ur) break;
    }
    for (i = dl;; i = (i == n) ? 1 : (i + 1)) {
      d[++nd] = p[i];
      if (i == dr) break;
    }
  } else {
    for (i = ul;; i = (i == n) ? 1 : (i + 1)) {
      u[++nu] = p[i];
      if (i == ur) break;
    }
    for (i = dl;; i = (i == 1) ? n : (i - 1)) {
      d[++nd] = p[i];
      if (i == dr) break;
    }
  }
  u[++nu] = p[ur];
  d[++nd] = p[dr];
  int lx = p[ul].x, rx = p[ur].x, pu = 1, pd = 1;
  for (i = lx; i < rx; i++) {
    if ((pu <= nu) && (i == u[pu + 1].x)) pu++;
    if ((pd <= nd) && (i == d[pd + 1].x)) pd++;
    ly[i + P] =
        d[pd].y + ceil((i - d[pd].x) * ((double)(d[pd + 1].y - d[pd].y) /
                                        (d[pd + 1].x - d[pd].x)) -
                       1e-6);
    ry[i + P] =
        u[pu].y + floor((i - u[pu].x) * ((double)(u[pu + 1].y - u[pu].y) /
                                         (u[pu + 1].x - u[pu].x)) +
                        1e-6);
  }
  ry[rx + P] = u[nu].y;
  ly[rx + P] = d[nd].y;
  double ret = 0;
  long long tot = 0;
  for (i = lx; i <= rx; i++)
    cnt[i - lx + 1] = ry[i + P] - ly[i + P] + 1, tot += cnt[i - lx + 1];
  double s1 = cnt[1], s2 = cnt[1], s = 0;
  for (i = 2; i <= rx - lx + 1; i++) {
    s += s2;
    s1 += cnt[i - 1] + cnt[i];
    s2 += s1;
    ret += s * cnt[i] / tot;
  }
  ans += ret / (tot - 1);
}
int main() {
  int i;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y), b[i] = true;
  for (i = 2; i < n; i++)
    if (cross(i - 1, i, i + 1) == 0) b[i] = false;
  if (cross(n - 1, n, 1) == 0) b[n] = false;
  if (cross(n, 1, 2) == 0) b[1] = false;
  int m = n;
  n = ans = 0;
  for (i = 1; i <= m; i++)
    if (b[i]) p[++n] = p[i];
  process();
  for (i = 1; i <= n; i++) swap(p[i].x, p[i].y);
  process();
  printf("%.10lf\n", ans);
  return 0;
}