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 {
  long long x, y;
} high, low, st, en, temp_up, temp_down;
long long n, k;
long long total = 0, cntx[2000002], cnty[2000002];
vector<point> v, up, down;
long long check(point a, point b, point c) {
  return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (long long i = 1, x, y; i <= n; i++) {
    cin >> x >> y;
    v.push_back({x + 1000000, y + 1000000});
  }
  sort(v.begin(), v.end(),
       [](point a, point b) { return a.x < b.x || (a.x == b.x && a.y < b.y); });
  st = v[0], en = v.back();
  for (long long i = 0; i < (long long)v.size(); i++) {
    if (i != (long long)v.size() - 1 && check(v[i], st, en) < 0) continue;
    while (up.size() > 2 &&
           check(up[up.size() - 1], up[up.size() - 2], v[i]) < 0) {
      up.pop_back();
    }
    up.push_back(v[i]);
  }
  for (long long i = 0; i < (long long)v.size(); i++) {
    if (i != (long long)v.size() - 1 && check(v[i], st, en) > 0) continue;
    while (down.size() > 2 &&
           check(down[down.size() - 1], down[down.size() - 2], v[i]) > 0) {
      down.pop_back();
    }
    down.push_back(v[i]);
  }
  high = low = {v[0].x + 1, v[0].y};
  long long cur = 0, mn = v[0].y, mx = v[0].y;
  while (1) {
    cur++;
    if (v[cur].x == v[cur - 1].x) {
      mx = max(mx, v[cur].y);
      mn = min(mn, v[cur].y);
    } else {
      break;
    }
  }
  high.y = mx;
  low.y = mn;
  cntx[v[0].x] = high.y - low.y + 1;
  while (high.x <= v.back().x && low.x <= v.back().x) {
    long long k = lower_bound(up.begin(), up.end(), (point){high.x, 0},
                              [](point a, point b) {
                                return a.x < b.x || (a.x == b.x && a.y < b.y);
                              }) -
                  up.begin();
    temp_up = high;
    while (check(up[k - 1], up[k], temp_up) <= 0) {
      high = temp_up;
      temp_up.y++;
    }
    while (check(up[k - 1], up[k], high) > 0) {
      temp_up.y--;
      high = temp_up;
    }
    k = lower_bound(down.begin(), down.end(), (point){low.x, 0},
                    [](point a, point b) {
                      return a.x < b.x || (a.x == b.x && a.y < b.y);
                    }) -
        down.begin();
    temp_down = low;
    while (check(down[k - 1], down[k], temp_down) >= 0) {
      low = temp_down;
      temp_down.y--;
    }
    while (check(down[k - 1], down[k], temp_down) < 0) {
      temp_down.y++;
      low = temp_down;
    }
    cntx[high.x] = high.y - low.y + 1;
    high.x++;
    low.x++;
  }
  up.clear();
  down.clear();
  sort(v.begin(), v.end(),
       [](point a, point b) { return a.y < b.y || (a.y == b.y && a.x < b.x); });
  st = v[0], en = v.back();
  for (long long i = 0; i < (long long)v.size(); i++) {
    if (i != (long long)v.size() - 1 && check(v[i], st, en) < 0) continue;
    while (up.size() > 2 &&
           check(up[up.size() - 1], up[up.size() - 2], v[i]) < 0) {
      up.pop_back();
    }
    up.push_back(v[i]);
  }
  for (long long i = 0; i < (long long)v.size(); i++) {
    if (i != (long long)v.size() - 1 && check(v[i], st, en) > 0) continue;
    while (down.size() > 2 &&
           check(down[down.size() - 1], down[down.size() - 2], v[i]) > 0) {
      down.pop_back();
    }
    down.push_back(v[i]);
  }
  high = low = {v[0].x, v[0].y + 1};
  cur = 0, mn = v[0].x, mx = v[0].x;
  while (1) {
    cur++;
    if (v[cur].y == v[cur - 1].y) {
      mx = max(mx, v[cur].x);
      mn = min(mn, v[cur].x);
    } else {
      break;
    }
  }
  low.x = mx;
  high.x = mn;
  cnty[v[0].y] = low.x - high.x + 1;
  total += cnty[v[0].y];
  while (high.y <= v.back().y && low.y <= v.back().y) {
    k = lower_bound(up.begin(), up.end(), (point){0, high.y},
                    [](point a, point b) {
                      return a.y < b.y || (a.y == b.y && a.x < b.x);
                    }) -
        up.begin();
    point temp_up = high, temp_down = low;
    while (check(up[k - 1], up[k], temp_up) <= 0) {
      high = temp_up;
      temp_up.x--;
    }
    while (check(up[k - 1], up[k], high) > 0) {
      temp_up.x++;
      high = temp_up;
    }
    k = lower_bound(down.begin(), down.end(), (point){0, low.y},
                    [](point a, point b) {
                      return a.y < b.y || (a.y == b.y && a.x < b.x);
                    }) -
        down.begin();
    while (check(down[k - 1], down[k], temp_down) >= 0) {
      low = temp_down;
      temp_down.x++;
    }
    while (check(down[k - 1], down[k], temp_down) < 0) {
      temp_down.x--;
      low = temp_down;
    }
    cnty[high.y] = low.x - high.x + 1;
    total += cnty[high.y];
    high.y++;
    low.y++;
  }
  long long sumx = 0, sumy = 0;
  double sumx_square = 0, sumy_square = 0;
  long double ansx = 0, ansy = 0;
  for (long long j = 0; j <= 2e6; j++) {
    sumx += (j - 1e6) * cntx[j];
    sumx_square +=
        (long double)(j - 1e6) * (j - 1e6) / (total - 1) / 2 * cntx[j];
    sumy += (j - 1e6) * cnty[j];
    sumy_square +=
        (long double)(j - 1e6) * (j - 1e6) / (total - 1) / 2 * cnty[j];
  }
  for (long long i = 0; i <= 2e6; i++) {
    ansx += (long double)((i - 1e6) * total - 2ll * sumx) / total * (i - 1e6) /
            (total - 1) * cntx[i] / 2;
    ansy += (long double)((i - 1e6) * total - 2ll * sumy) / total * (i - 1e6) /
            (total - 1) * cnty[i] / 2;
  }
  ansx += sumx_square;
  ansy += sumy_square;
  long double t = ansx + ansy;
  cout << fixed << setprecision(10) << t << '\n';
}