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>
const int N = 100000 + 9;
int n, n2;
long double sum, ans;
struct point {
  int x, y;
  point(const int _x, const int _y) : x(_x), y(_y) {}
  point() {}
} p[N * 2];
inline long long cpr(const point &a, const point &b, const point &c) {
  return 1ll * (b.x - a.x) * (c.y - a.y) - 1ll * (c.x - a.x) * (b.y - a.y);
}
inline double sqr(const double x) { return x * x; }
void work1() {
  sum = 0;
  int l = 1, r = 1, Max = -99999999;
  for (int i = 1; i <= n2; ++i) {
    if (p[i].x < p[l].x) l = i;
    if (p[i].x <= p[r].x) r = i;
    Max = std::max(Max, p[i].x);
  }
  if (p[l].x == p[l + 1].x) ++l;
  if (p[r].x == p[r - 1].x) --r;
  for (int i = p[l].x; i <= Max; ++i) {
    if (p[l + 1].x < i) ++l;
    if (p[r - 1].x < i) --r;
    int bot = std::ceil((p[l + 1].y - p[l].y) * 1.0 / (p[l + 1].x - p[l].x) *
                            (i - p[l].x) +
                        p[l].y);
    int top = std::floor((p[r - 1].y - p[r].y) * 1.0 / (p[r - 1].x - p[r].x) *
                             (i - p[r].x) +
                         p[r].y);
    sum += (top - bot + 1);
  }
}
void work() {
  int l = 1, r = 1, Max = -99999999;
  for (int i = 1; i <= n2; ++i) {
    if (p[i].x < p[l].x) l = i;
    if (p[i].x <= p[r].x) r = i;
    Max = std::max(Max, p[i].x);
  }
  if (p[l].x == p[l + 1].x) ++l;
  if (p[r].x == p[r - 1].x) --r;
  long double sum1 = 0, sum2 = 0, sum3 = 0;
  for (int i = p[l].x; i <= Max; ++i) {
    if (p[l + 1].x < i) ++l;
    if (p[r - 1].x < i) --r;
    int bot = std::ceil((p[l + 1].y - p[l].y) * 1.0 / (p[l + 1].x - p[l].x) *
                            (i - p[l].x) +
                        p[l].y);
    int top = std::floor((p[r - 1].y - p[r].y) * 1.0 / (p[r - 1].x - p[r].x) *
                             (i - p[r].x) +
                         p[r].y);
    sum1 += sum2;
    sum2 += sum3 * 2 + (top - bot + 1);
    sum3 += (top - bot + 1);
    ans += (top - bot + 1) / (sum * (sum - 1)) * sum1;
  }
}
int main() {
  scanf("%d", &n);
  n2 = 2 * n;
  for (int i = 1; i <= n; ++i) scanf("%d%d", &p[i].x, &p[i].y);
  p[n + 1] = p[1];
  long long S = 0;
  for (int i = 1; i <= n; ++i) S += cpr(point(0, 0), p[i], p[i + 1]);
  if (S < 0) std::reverse(p + 1, p + 1 + n);
  for (int i = 1; i <= n; ++i) {
    p[i + n] = p[i];
  }
  work1();
  work();
  for (int i = 1; i <= n2; ++i) {
    std::swap(p[i].x, p[i].y);
    p[i].x = -p[i].x;
  }
  work();
  printf("%.8f\n", (double)(ans));
}