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;
typedef struct point {
  int x, y;
  point(int x0, int y0) {
    x = x0;
    y = y0;
  }
} PT;
class Line {
 public:
  double A, B, C;
  Line(double x1, double y1, double x2, double y2) {
    A = y2 - y1;
    B = x1 - x2;
    C = A * x1 + B * y1;
  }
  double getY(double x) { return (C - A * x) / B; }
  double getX(double y) { return (C - B * y) / C; }
};
double horizontal[2000005][2], result;
int integralHorizontalPoints[2000005];
vector<PT> polygon;
double totalArea, totalIntegreal;
void preprocess(int n) {
  int i, j, l, r, k, x, y, minX = 2000005, maxX = -2000005;
  double difference = 0.0, doubleDiff = 0.0, oldArea = 0.0;
  for (i = 0; i < 2000005; i++) {
    horizontal[i][0] = 1.0 * 2000005;
    horizontal[i][1] = -1.0 * 2000005;
  }
  for (i = 0; i < n; i++) {
    minX = min(minX, polygon[i].x);
    maxX = max(maxX, polygon[i].x);
    j = i + 1;
    if (j == n) j = 0;
    Line L(1.0 * polygon[i].x, 1.0 * polygon[i].y, 1.0 * polygon[j].x,
           1.0 * polygon[j].y);
    l = min(polygon[i].x, polygon[j].x);
    r = max(polygon[i].x, polygon[j].x);
    if (l == r) {
      if (polygon[i].y < polygon[j].y) {
        x = polygon[i].y;
        y = polygon[j].y;
      } else {
        x = polygon[j].y;
        y = polygon[i].y;
      }
      horizontal[l][0] = min(horizontal[l][0], 1.0 * x);
      horizontal[l][1] = max(horizontal[l][1], 1.0 * y);
    } else {
      for (k = l; k <= r; k++) {
        horizontal[k][0] = min(horizontal[k][0], L.getY(k));
        horizontal[k][1] = max(horizontal[k][1], L.getY(k));
      }
    }
  }
  for (i = minX; i <= maxX; i++) {
    integralHorizontalPoints[i] =
        floor(horizontal[i][1]) - ceil(horizontal[i][0]) + 1;
    totalIntegreal += 1.0 * integralHorizontalPoints[i];
  }
  oldArea = 1.0 * integralHorizontalPoints[minX];
  totalArea += 1.0 * oldArea * integralHorizontalPoints[minX + 1];
  difference = integralHorizontalPoints[minX];
  for (i = minX + 2; i <= maxX; i++) {
    doubleDiff += 2.0 * integralHorizontalPoints[i - 2];
    difference += doubleDiff + 1.0 * integralHorizontalPoints[i - 1];
    oldArea += difference;
    totalArea += 1.0 * oldArea * integralHorizontalPoints[i];
  }
  return;
}
double nc2(double n) { return n * (n - 1.0); }
int main() {
  int i, j, t, n, m, k, l, r, temp, mini, maxi, flag, cnt, x, y;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d%d", &l, &r);
    l += 1000000;
    r += 1000000;
    PT foo(l, r);
    polygon.push_back(foo);
  }
  preprocess(n);
  for (i = 0; i < n; i++) swap(polygon[i].x, polygon[i].y);
  preprocess(n);
  totalIntegreal /= 2.0;
  result = totalArea / nc2(totalIntegreal);
  printf("%.8lf\n", result);
  return 0;
}