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 ding = 1000005;
const double eps = 1e-8;
long long n, m, z, x[100005], y[100005], a[2000011], l, r, mi, sum, node, t;
long long tx[100005], ty[100005];
long double ans, zc;
double fans;
inline int pre(int l) {
  if (l > 1)
    return l - 1;
  else
    return n;
}
inline int next(int l) {
  if (l < n)
    return l + 1;
  else
    return 1;
}
inline int workx(int p, int l, int r) {
  int a, b;
  if (x[l] == x[pre(l)])
    a = min(y[l], y[pre(l)]) - 1;
  else
    a = ceil(y[l] + (y[pre(l)] - y[l]) / (1.0 * x[pre(l)] - x[l]) * (p - x[l]) -
             eps) -
        1;
  if (x[r] == x[next(r)])
    b = max(y[r], y[next(r)]);
  else
    b = floor(y[r] +
              (y[next(r)] - y[r]) / (1.0 * x[next(r)] - x[r]) * (p - x[r]) +
              eps);
  return b - a;
}
inline int worky(int p, int l, int r) {
  int a, b;
  if (y[l] == y[pre(l)])
    a = max(x[l], x[pre(l)]);
  else
    a = floor(x[l] +
              (x[pre(l)] - x[l]) * (p - y[l]) / (1.0 * y[pre(l)] - y[l]));
  if (y[r] == y[next(r)])
    b = min(x[r], x[next(r)]) - 1;
  else
    b = ceil(x[r] +
             (x[next(r)] - x[r]) * (p - y[r]) / (1.0 * y[next(r)] - y[r])) -
        1;
  return a - b;
}
inline void work() {
  zc = 0;
  for (long long i = 0; i <= 2 * ding; ++i)
    if (a[i] > 0) {
      z = i - ding;
      zc += 1.0 * a[i] * z * z;
      sum += a[i] * z;
    }
  ans += zc / (node * 1.0);
  zc = 0;
  for (long long i = 0; i <= 2 * ding; ++i)
    if (a[i] > 0) {
      z = i - ding;
      zc += 1.0 * a[i] * z * (sum - z);
    }
  ans -= zc / (node * 1.0) / ((node - 1) * 1.0);
}
int main() {
  scanf("%I64d", &n);
  mi = 2 * ding;
  for (int i = 1; i <= n; ++i) {
    scanf("%I64d%I64d", &x[i], &y[i]);
    if (x[i] + ding < mi) mi = x[i] + ding, l = i;
  }
  for (int i = 1; i <= n; ++i)
    tx[i] = x[(i + l - 2) % n + 1], ty[i] = y[(i + l - 2) % n + 1];
  for (int i = 1; i <= n; ++i) x[i] = tx[i], y[i] = ty[i];
  if (y[2] < y[n])
    for (int i = 2; i <= (n + 1) / 2; ++i)
      swap(x[i], x[n - i + 2]), swap(y[i], y[n - i + 2]);
  t = x[1];
  r = l = 1;
  for (int i = 1; i <= n - 1; ++i) {
    if (x[pre(l)] <= x[next(r)]) {
      for (int j = t; j < x[pre(l)]; ++j) a[j + ding] = workx(j, l, r);
      l = pre(l);
      t = x[l];
    } else {
      for (int j = t; j < x[next(r)]; ++j) a[j + ding] = workx(j, l, r);
      r = next(r);
      t = x[r];
    }
  }
  a[x[l] + ding] = workx(x[l], next(l), r);
  node = 0;
  for (long long i = 0; i <= 2 * ding; ++i) node += a[i];
  work();
  memset(a, 0, sizeof(a));
  sum = 0;
  mi = 2 * ding;
  for (int i = 1; i <= n; ++i)
    if (y[i] + ding < mi) mi = y[i] + ding, l = i;
  r = l;
  t = y[l];
  for (int i = 1; i <= n - 1; ++i) {
    if (y[pre(l)] <= y[next(r)]) {
      for (int j = t; j < y[pre(l)]; ++j) a[j + ding] = worky(j, l, r);
      l = pre(l);
      t = y[l];
    } else {
      for (int j = t; j < y[next(r)]; ++j) a[j + ding] = worky(j, l, r);
      r = next(r);
      t = y[r];
    }
  }
  a[y[l] + ding] = worky(y[l], next(l), r);
  work();
  fans = ans;
  printf("%.10lf", fans);
}