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;
inline int read() {
  static int r, sign;
  static char c;
  r = 0, c = getchar(), sign = 1;
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') sign = -1, c = getchar();
  while (c >= '0' && c <= '9') r = r * 10 + (c - '0'), c = getchar();
  return r * sign;
}
template <typename T>
inline void print(T *a, int n) {
  for (int i = 1; i < n; ++i) cout << a[i] << " ";
  cout << a[n] << endl;
}
struct point {
  int x, y;
  inline void read() { scanf("%d%d", &x, &y); }
} p, q, t;
int n, u[2000010 + 1], d[2000010 + 1], l[2000010 + 1], r[2000010 + 1], U, R, L,
    D;
inline void process(const point &p, const point &q) {
  if (p.x == q.x) {
    u[p.x + 1000000] = max(u[p.x + 1000000], max(p.y, q.y));
    d[p.x + 1000000] = min(d[p.x + 1000000], min(p.y, q.y));
  } else {
    double ma = max(p.x, q.x), mi = min(p.x, q.x), s = p.x < q.x ? p.y : q.y;
    for (int i = mi; i <= ma; ++i) {
      double y = s + (double)(i - mi) * (q.y - p.y) / (q.x - p.x);
      u[i + 1000000] = max(u[i + 1000000], (int)floor(y));
      d[i + 1000000] = min(d[i + 1000000], (int)ceil(y));
    }
  }
  if (p.y == q.y) {
    r[p.y + 1000000] = max(r[p.y + 1000000], max(p.x, q.x));
    l[p.y + 1000000] = min(l[p.y + 1000000], min(p.x, q.x));
  } else {
    double ma = max(p.y, q.y), mi = min(p.y, q.y), s = p.y < q.y ? p.x : q.x;
    for (int i = mi; i <= ma; ++i) {
      double x = s + (double)(i - mi) * (q.x - p.x) / (q.y - p.y);
      r[i + 1000000] = max(r[i + 1000000], (int)floor(x));
      l[i + 1000000] = min(l[i + 1000000], (int)ceil(x));
    }
  }
}
inline void process(const point &p) {
  U = max(U, p.y), D = min(D, p.y);
  R = max(R, p.x), L = min(L, p.x);
}
double s[4][2000010 + 1];
double solve(int n) {
  for (int i = 0; i < 4; ++i) s[i][n + 1] = 0;
  for (int i = n; i > 0; --i) s[1][i] = s[1][i + 1] + s[0][i];
  if (s[1][1] <= 1) return 0.0;
  for (int i = n; i > 0; --i) s[2][i] = s[2][i + 1] + 2 * s[1][i] - s[0][i];
  double tot = s[1][1] * (s[1][1] - 1);
  for (int i = n; i > 0; --i) s[2][i] /= tot;
  for (int i = n; i > 0; --i) s[3][i] = s[3][i + 1] + s[2][i];
  double ret = 0.0;
  for (int i = n - 1; i > 0; --i) ret += s[0][i] * s[3][i + 1];
  return ret;
}
int main(int argc, char *argv[]) {
  for (int i = 0; i <= 2000010; ++i)
    u[i] = r[i] = INT_MIN, d[i] = l[i] = INT_MAX;
  U = R = INT_MIN, D = L = INT_MAX;
  scanf("%d", &n);
  p.read(), t = p, process(t);
  for (int i = 2; i <= n; ++i) {
    q.read(), process(q);
    process(p, q);
    p = q;
  }
  process(q, t);
  double ans = 0.0;
  int cnt = 0;
  for (int i = L; i <= R; ++i)
    s[0][++cnt] = (double)(u[i + 1000000] - d[i + 1000000] + 1);
  ans += solve(cnt);
  cnt = 0;
  for (int i = D; i <= U; ++i)
    s[0][++cnt] = (double)(r[i + 1000000] - l[i + 1000000] + 1);
  ans += solve(cnt);
  printf("%.10lf\n", ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}