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;
struct Point {
  int x, y;
  Point() {}
  Point(int x, int y) {
    this->x = x;
    this->y = y;
  }
  Point operator+(Point rhs) { return Point(x + rhs.x, y + rhs.y); }
  Point operator-(Point rhs) { return Point(x - rhs.x, y - rhs.y); }
  long long Dot(Point rhs) { return 1LL * x * rhs.x + 1LL * y * rhs.y; }
  long long Crs(Point rhs) { return 1LL * x * rhs.y - 1LL * y * rhs.x; }
};
bool operator<(Point lhs, Point rhs) {
  return (lhs.x == rhs.x) ? (lhs.y < rhs.y) : (lhs.x < rhs.x);
}
const int MAXN = 100010;
int N;
Point p[MAXN];
vector<Point> H[2];
int pcx[2333333], pcy[2333333];
int *cx = pcx + 1233333, *cy = pcy + 1233333;
long long cip;
double Stat(int* e, int Min, int Max) {
  double ret = 0;
  double Count = 0, sumPlain = 0, sumSquare = 0;
  int i;
  for (i = Min; i <= Max; i++) {
    ret += e[i] * (Count * i * i + sumSquare - 2.0 * i * sumPlain);
    Count += e[i];
    sumPlain += e[i] * 1.0 * i;
    sumSquare += e[i] * 1.0 * i * i;
  }
  return ret;
}
int main() {
  scanf("%d", &N);
  int i;
  for (i = 1; i <= N; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    p[i] = Point(x, y);
  }
  sort(p + 1, p + N + 1);
  int ml = 1;
  while ((ml < N) && (p[ml + 1].x == p[1].x)) ml++;
  H[0].clear();
  H[1].clear();
  H[0].push_back(p[1]);
  H[1].push_back(p[ml]);
  for (i = ml + 1; i <= N; i++) {
    while ((H[0].size() > 1) &&
           ((H[0].back() - H[0][H[0].size() - 2]).Crs(p[i] - H[0].back()) <= 0))
      H[0].pop_back();
    while ((H[1].size() > 1) &&
           ((H[1].back() - H[1][H[1].size() - 2]).Crs(p[i] - H[1].back()) >= 0))
      H[1].pop_back();
    H[0].push_back(p[i]);
    H[1].push_back(p[i]);
  }
  while ((H[0].size() > 1) && (H[0].back().x == H[0][H[0].size() - 2].x))
    H[0].pop_back();
  vector<Point>::iterator lit = H[0].begin(), rit = H[1].begin();
  int minX = p[1].x, maxX = p[N].x, minY = p[1].y, maxY = p[1].y;
  for (i = 2; i <= N; i++) {
    minY = min(minY, p[i].y);
    maxY = max(maxY, p[i].y);
  }
  for (i = minY; i <= maxY; i++) cy[i] = 0;
  cx[maxX] = H[1].back().y - H[0].back().y + 1;
  cy[H[1].back().y + 1]--;
  cy[H[0].back().y]++;
  for (i = minX; i <= maxX - 1; i++) {
    if ((lit + 1)->x <= i) lit++;
    if ((rit + 1)->x <= i) rit++;
    int ly = ceil(double((lit + 1)->y - lit->y) / ((lit + 1)->x - lit->x) *
                      (i - lit->x) +
                  lit->y - 1e-9);
    int ry = floor(double((rit + 1)->y - rit->y) / ((rit + 1)->x - rit->x) *
                       (i - rit->x) +
                   rit->y + 1e-9);
    cx[i] = ry - ly + 1;
    cy[ry + 1]--;
    cy[ly]++;
  }
  for (i = minY + 1; i <= maxY; i++) cy[i] += cy[i - 1];
  cip = 0;
  for (i = minX; i <= maxX; i++) cip += cx[i];
  double ans = Stat(cx, minX, maxX) + Stat(cy, minY, maxY);
  ans /= cip;
  ans /= cip - 1;
  printf("%.10f\n", ans);
}