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;
const int inf = 1000000000;
struct pt {
  int x, y;
  pt() {}
  pt(int x, int y) : x(x), y(y) {}
  friend bool operator<(const pt &a, const pt &b) {
    if (a.y == b.y) return a.x < b.x;
    return a.y < b.y;
  }
};
struct seg {
  pt a, b;
  long long A, B, C;
  seg() {}
  seg(pt a, pt b) : a(a), b(b) {
    A = a.y - b.y;
    B = b.x - a.x;
    C = A * a.x + B * a.y;
  }
  int cut_r(int y) {
    int x = (C - B * y) / A;
    if (A * x + B * y < C) ++x;
    return x;
  }
  int cut_l(int y) {
    int x = (C - B * y) / A;
    if (A * x + B * y > C) --x;
    return x;
  }
};
int n, x, y;
vector<pt> p;
vector<seg> L;
vector<seg> R;
double tot;
double sum_range(int l, int r) {
  if (l > r) return 0;
  double len = r - l + 1;
  return len * l + len * (len - 1) * 0.5;
}
double _sum_squares(int n) {
  double ret = (double)(n + 1) * n * (n - 1) / 3;
  ret += (double)n * (n + 1) / 2;
  return ret;
}
double sum_squares(int l, int r) {
  if (l > r) return 0;
  if (l <= 0 && r >= 0) return _sum_squares(abs(l)) + _sum_squares(abs(r));
  l = abs(l);
  r = abs(r);
  if (l > r) swap(l, r);
  double ret = _sum_squares(r);
  if (l) ret -= _sum_squares(l - 1);
  return ret;
}
double solve() {
  int miny = +inf;
  int maxy = -inf;
  long long area = 0;
  for (int i = (0); i < (n); ++i) {
    miny = min(miny, p[i].y);
    maxy = max(maxy, p[i].y);
    int j = (i + 1) % n;
    area += (long long)p[i].x * p[j].y - (long long)p[i].y * p[j].x;
  }
  if (area < 0) reverse(p.begin(), p.end());
  L.clear();
  R.clear();
  rotate(p.begin(), max_element(p.begin(), p.end()), p.end());
  for (int i = ((p[0].y == p[1].y)); i < (n); ++i) {
    if (p[i].y == miny) break;
    L.push_back(seg(p[i], p[i + 1]));
  }
  R.push_back(seg(p[0], p.back()));
  for (int i = (0); i < (n); ++i) {
    if (p[n - i - 1].y == miny) break;
    R.push_back(seg(p[n - i - 1], p[n - i - 2]));
  }
  tot = 0.0;
  double sum = 0.0;
  double sum_sq = 0.0;
  int li = 0, ri = 0;
  for (int y = maxy; y >= miny; --y) {
    if (y < L[li].b.y) ++li;
    if (y < R[ri].b.y) ++ri;
    int l = L[li].cut_r(y);
    int r = R[ri].cut_l(y);
    tot += r - l + 1;
    sum += sum_range(l, r);
    sum_sq += sum_squares(l, r);
  }
  return 2.0 * sum_sq - 2.0 * (sum / tot) * sum;
}
int main(void) {
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) {
    scanf("%d%d", &x, &y);
    p.push_back(pt(x, y));
  }
  double sol = 0.0;
  sol += solve();
  for (int i = (0); i < (n); ++i) swap(p[i].x, p[i].y);
  sol += solve();
  sol /= (tot - 1.0);
  sol *= 0.5;
  printf("%.8lf\n", sol);
  return 0;
}