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;
template <class T>
inline T LOW_BIT(T n);
template <class T>
inline int COUNT_BIT(T n);
template <class T>
inline T GCD(T a, T b);
template <class T>
inline T LCM(T a, T b);
bool isUpperCase(char c);
bool isLowerCase(char c);
bool isLetter(char c);
bool isDigit(char c);
char toLowerCase(char c);
char toUpperCase(char c);
template <class T>
string toString(T n);
template <class T>
void stoa(const string &s, int &n, T A[]);
template <class T>
void atos(int n, T A[], string &s);
template <class T>
void atov(int n, T A[], vector<T> &vi);
template <class T>
void vtoa(const vector<T> &vi, int &n, T A[]);
template <class T>
void stov(const string &s, vector<T> &vi);
template <class T>
void vtos(const vector<T> &vi, string &s);
template <class T>
inline vector<pair<T, int> > factorize(T n);
int64_t inverse_mod(int64_t a, int64_t mod);
string testCaseOutTemp = "Case #%d: ";
int numThread = 4;
void initProgram() {}
class Task {
 public:
  ostringstream out;
  int testcase;
  int N;
  int X[100010];
  int Y[100010];
  int64_t lo[2 * 1000010];
  int64_t hi[2 * 1000010];
  int64_t a[2 * 1000010];
  int64_t sum[2 * 1000010];
  double T[2 * 1000010];
  double P[2 * 1000010];
  double Q[2 * 1000010];
  int64_t area() {
    int64_t a = 0, b = 0;
    for (int i = 0, __e__ = (int)(N); i < __e__; ++i) {
      a += int64_t(X[i]) * int64_t(Y[(i + 1) % N]);
      b += int64_t(Y[i]) * int64_t(X[(i + 1) % N]);
    }
    return a - b;
  }
  void readInput() {
    scanf("%d", &N);
    for (int i = 0, __e__ = (int)(N); i < __e__; ++i) {
      scanf("%d %d", X + i, Y + i);
      X[i] += 1000010;
      Y[i] += 1000010;
    }
  }
  void pre() {
    int64_t ar = area();
    if (ar > 0) {
      reverse(X, X + N);
      reverse(Y, Y + N);
    }
    memset(lo, 0, sizeof lo);
    for (int i = 0, __e__ = (int)(2 * 1000010); i < __e__; ++i) hi[i] = -1;
    for (int i = 0, __e__ = (int)(N); i < __e__; ++i) {
      int next = (i + 1) % N;
      int64_t A = -(Y[i] - Y[next]);
      int64_t B = (X[i] - X[next]);
      int64_t C = A * int64_t(X[i]) + B * int64_t(Y[i]);
      if (X[i] == X[next]) {
        lo[X[i]] = min(Y[i], Y[next]);
        hi[X[i]] = max(Y[i], Y[next]);
      } else if (X[i] < X[next]) {
        for (int x = (X[i]), __e__ = (int)(X[next]); x <= __e__; ++x) {
          hi[x] = (-A * int64_t(x) + C) / B;
        }
      } else {
        for (int x = (X[next]), __e__ = (int)(X[i]); x <= __e__; ++x) {
          int64_t temp = (-A * int64_t(x) + C);
          lo[x] = temp / B;
          if (temp % B != 0) {
            lo[x]++;
          }
        }
      }
    }
  }
  double calcs() {
    for (int i = 0, __e__ = (int)(2 * 1000010); i < __e__; ++i) {
      a[i] = hi[i] - lo[i] + 1LL;
    }
    sum[0] = a[0];
    for (int i = (1), __e__ = (int)(2 * 1000010 - 1); i <= __e__; ++i) {
      sum[i] = a[i] + sum[i - 1];
    }
    T[1] = a[0];
    P[2] = a[1] + 3 * a[0];
    T[2] = T[1] + P[2];
    for (int i = (3), __e__ = (int)(2 * 1000010); i <= __e__; ++i) {
      Q[i] = a[i - 1] + 2.0 * sum[i - 2];
      P[i] = P[i - 1] + Q[i];
      T[i] = T[i - 1] + P[i];
    }
    double ss = 0;
    for (int i = (1), __e__ = (int)(2 * 1000010); i <= __e__; ++i) {
      ss += (double)a[i] * T[i];
    }
    return ss;
  }
  void process() {
    double ss = 0;
    pre();
    ss += calcs();
    for (int i = 0, __e__ = (int)(N); i < __e__; ++i) {
      swap(X[i], Y[i]);
    }
    pre();
    ss += calcs();
    int64_t cnt = sum[2 * 1000010 - 1];
    out << fixed << ss / (double)cnt / (double)(cnt - 1LL);
  }
};
int main() {
  srand(time(0));
  initProgram();
  int ntest = 1;
  {} {
    for (int i = 0, __e__ = (int)(ntest); i < __e__; ++i) {
      cerr << "processing test: " << i + 1 << endl;
      Task *pT = new Task();
      pT->testcase = i + 1;
      pT->readInput();
      pT->process();
      cout << pT->out.str();
      delete pT;
    }
  }
}
template <class T>
inline T LOW_BIT(T n) {
  return (n ^ (n - 1)) & n;
}
template <class T>
inline int COUNT_BIT(T n) {
  return (n == 0) ? 0 : (1 + COUNT_BIT(n & (n - 1)));
}
template <class T>
inline T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (b == 0) ? a : GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return a * (b / GCD(a, b));
}
bool isUpperCase(char c) { return c >= 'A' && c <= 'Z'; }
bool isLowerCase(char c) { return c >= 'a' && c <= 'z'; }
bool isLetter(char c) {
  return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
}
bool isDigit(char c) { return c >= '0' && c <= '9'; }
char toLowerCase(char c) { return (isUpperCase(c)) ? (c + 32) : c; }
char toUpperCase(char c) { return (isLowerCase(c)) ? (c - 32) : c; }
template <class T>
string toString(T n) {
  ostringstream ost;
  ost << n;
  ost.flush();
  return ost.str();
}
template <class T>
inline vector<pair<T, int> > factorize(T n) {
  vector<pair<T, int> > R;
  for (T i = 2; n > 1;) {
    if (n % i == 0) {
      int C = 0;
      for (; n % i == 0; C++, n /= i)
        ;
      R.push_back(make_pair(i, C));
    }
    i++;
    if (i > n / i) i = n;
  }
  if (n > 1) R.push_back(make_pair(n, 1));
  return R;
}
template <class T>
void stoa(const string &s, int &n, T A[]) {
  n = 0;
  istringstream sin(s);
  for (T v; sin >> v; A[n++] = v)
    ;
}
template <class T>
void atos(int n, T A[], string &s) {
  ostringstream sout;
  for (int i = 0; i < n; i++) {
    if (i > 0) sout << ' ';
    sout << A[i];
  }
  s = sout.str();
}
template <class T>
void atov(int n, T A[], vector<T> &vi) {
  vi.clear();
  for (int i = 0; i < n; i++) vi.push_back(A[i]);
}
template <class T>
void vtoa(const vector<T> &vi, int &n, T A[]) {
  n = vi.size();
  for (int i = 0; i < n; i++) A[i] = vi[i];
}
template <class T>
void stov(const string &s, vector<T> &vi) {
  vi.clear();
  istringstream sin(s);
  for (T v; sin >> v; vi.push_bakc(v))
    ;
}
template <class T>
void vtos(const vector<T> &vi, string &s) {
  ostringstream sout;
  for (int i = 0; i < vi.size(); i++) {
    if (i > 0) sout << ' ';
    sout << vi[i];
  }
  s = sout.str();
}
struct extended_gcd_res {
  int64_t x;
  int64_t y;
  extended_gcd_res(int64_t _x, int64_t _y) {
    x = _x;
    y = _y;
  }
};
extended_gcd_res extended_gcd(int64_t a, int64_t b) {
  if (b == 0)
    return extended_gcd_res(1, 0);
  else {
    int64_t q = a / b;
    int64_t r = a - b * q;
    extended_gcd_res res = extended_gcd(b, r);
    return extended_gcd_res(res.y, res.x - q * res.y);
  }
}
int64_t inverse_mod(int64_t a, int64_t mod) {
  extended_gcd_res res = extended_gcd(mod, a);
  if (res.y < 0) res.y += mod;
  return res.y;
}