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>
T abs(T x) {
  return x > 0 ? x : -x;
}
int n;
int m;
int x[100001];
int y[100001];
int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
int up(pair<int, int> a, pair<int, int> b, int c) {
  long long p = (long long)a.second * (b.first - a.first) +
                (long long)(b.second - a.second) * (c - a.first);
  long long q = b.first - a.first;
  if (p < 0) return p / q;
  return (p + q - 1) / q;
}
int down(pair<int, int> a, pair<int, int> b, int c) {
  long long p = (long long)a.second * (b.first - a.first) +
                (long long)(b.second - a.second) * (c - a.first);
  long long q = b.first - a.first;
  if (p > 0) return p / q;
  return (p - q + 1) / q;
}
double calc() {
  int a = 0, b = 0, c = 0, d = 0;
  for (int i = 0; i < n; i++) {
    if (x[i] < x[a] || (x[i] == x[a] && y[i] < y[a])) a = i;
    if (x[i] > x[b] || (x[i] == x[b] && y[i] < y[b])) b = i;
    if (x[i] < x[c] || (x[i] == x[c] && y[i] > y[c])) c = i;
    if (x[i] > x[d] || (x[i] == x[d] && y[i] > y[d])) d = i;
  }
  vector<pair<int, int> > v, w;
  for (int i = a; i != b; i = (i + 1) % n) v.push_back(make_pair(x[i], y[i]));
  v.push_back(make_pair(x[b], y[b]));
  for (int i = d; i != c; i = (i + 1) % n) w.push_back(make_pair(x[i], y[i]));
  w.push_back(make_pair(x[c], y[c]));
  reverse((w).begin(), (w).end());
  int i = 0, j = 0;
  double s = 0, sx = 0, sxx = 0, ans = 0;
  for (int c = x[a]; c <= x[b]; c++) {
    while (v[i + 1].first < c) i++;
    while (w[j + 1].first < c) j++;
    int l = up(v[i], v[i + 1], c);
    int r = down(w[j], w[j + 1], c);
    int cur = r - l + 1;
    ans += cur * (s * (c + 0.0) * c - 2 * sx * c + sxx);
    s += cur;
    sx += (c + 0.0) * cur;
    sxx += ((c + 0.0) * (c + 0.0)) * cur;
  }
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]);
  x[n] = x[0];
  y[n] = y[0];
  double sum = 0;
  for (int i = 0; i < n; i++)
    sum += (double)x[i] * y[i + 1] - (double)x[i + 1] * y[i];
  if (sum < 0) {
    reverse(x, x + n + 1);
    reverse(y, y + n + 1);
    sum = -sum;
  }
  sum /= 2;
  double cnt = 0;
  for (int i = 0; i < n; i++)
    cnt += gcd(abs(x[i + 1] - x[i]), abs(y[i + 1] - y[i]));
  cnt += (sum + 1 - cnt / 2);
  double ans = calc();
  for (int i = 0; i <= n; i++) swap(x[i], y[i]);
  reverse(x, x + n + 1);
  reverse(y, y + n + 1);
  ans += calc();
  printf("%.10f\n", ans / (cnt * (cnt - 1) / 2) / 2);
  return 0;
}