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;
int x[1000001 << 1], y[1000001 << 1], cx[1000001], cy[1000001];
long long CNT;
long double TWO, ONE;
vector<long double> xx[2000001];
int get(long double v1, long double v2) {
  return (int)(floor(v2 + 1e-9) - ceil(v1 - 1e-9)) + 1;
}
void go(int px[], int py[], int n) {
  long double two = 0, sum = 0, sec = 0;
  int i, j;
  long long cnt = 0;
  if ((long long)(px[0] - px[1]) * (py[2] - py[1]) -
          (long long)(px[2] - px[1]) * (py[0] - py[1]) >
      0) {
    for (i = 1; i < n - i; i++) {
      swap(px[i], px[n - i]);
      swap(py[i], py[n - i]);
    }
  }
  for (i = 0; i <= 2000000; i++) xx[i].clear();
  for (i = 0; i < n; i++) {
    if (px[i] < px[i + 1]) {
      for (j = px[i]; j <= px[i + 1]; j++) {
        xx[j + 1000001].push_back(py[i] + (py[i + 1] - py[i]) * 1. *
                                              (j - px[i]) /
                                              (px[i + 1] - px[i]));
      }
    } else if (px[i] > px[i + 1]) {
      for (j = px[i + 1]; j <= px[i]; j++) {
        xx[j + 1000001].push_back(py[i] + (py[i + 1] - py[i]) * 1. *
                                              (j - px[i]) /
                                              (px[i + 1] - px[i]));
      }
    } else {
      xx[px[i] + 1000001].push_back(py[i]);
      xx[px[i] + 1000001].push_back(py[i + 1]);
    }
  }
  for (i = 0; i <= 2000000; i++) {
    if (xx[i].size()) {
      long long ker = i - 1000001;
      sort(xx[i].begin(), xx[i].end());
      int now = get(xx[i][0], xx[i].back());
      long long nt_cnt = cnt + now;
      long double nt_two = two + ((long double)ker * ker * cnt -
                                  (long double)ker * sum * 2 + sec) *
                                     now;
      long double nt_sec = sec + (long double)ker * ker * now;
      long double nt_sum = sum + (long double)ker * now;
      cnt = nt_cnt;
      two = nt_two;
      sec = nt_sec;
      sum = nt_sum;
    }
  }
  CNT = cnt;
  TWO += two;
}
int main() {
  int i, j, k, n, No, miX = 100000000, miY;
  cin >> n;
  for (i = 0; i < n; i++) {
    scanf("%d%d", &x[i], &y[i]);
    cx[i] = x[i];
    cy[i] = y[i];
    x[n + i] = x[i];
    y[n + i] = y[i];
    if (x[i] < miX || (x[i] == miX && y[i] < miY)) {
      miX = x[i];
      miY = y[i];
      No = i;
    }
  }
  go(x + No, y + No, n);
  miX = 100000000;
  for (i = 0; i < n; i++) {
    x[i] = cy[i];
    y[i] = cx[i];
    x[n + i] = x[i];
    y[n + i] = y[i];
    if (x[i] < miX || (x[i] == miX && y[i] < miY)) {
      miX = x[i];
      miY = y[i];
      No = i;
    }
  }
  go(x + No, y + No, n);
  printf("%.15lf\n", (double)(TWO * 0.5 / ((long double)CNT * (CNT - 1) / 2)));
  return 0;
}