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 MAXN = 100010, MAXV = 1000010;
const double eps = 1e-8, PI = atan2(0, -1);
vector<double> x[MAXV * 2], y[MAXV * 2];
int cx[MAXV * 2], cy[MAXV * 2];
inline double sqr(double x) { return x * x; }
inline bool zero(double x) { return (x > 0 ? x : -x) < eps; }
inline int sgn(double x) { return (x > eps ? 1 : (x + eps < 0 ? -1 : 0)); }
struct point {
  double x, y;
  point(double x, double y) : x(x), y(y) {}
  point() {}
  bool operator==(const point& a) const {
    return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;
  }
  bool operator!=(const point& a) const {
    return sgn(x - a.x) != 0 || sgn(y - a.y) != 0;
  }
  bool operator<(const point& a) const {
    return sgn(x - a.x) < 0 || sgn(x - a.x) == 0 && sgn(y - a.y) < 0;
  }
  point operator+(const point& a) const { return point(x + a.x, y + a.y); }
  point operator-(const point& a) const { return point(x - a.x, y - a.y); }
  point operator*(const double& a) const { return point(x * a, y * a); }
  point operator/(const double& a) const { return point(x / a, y / a); }
  double operator*(const point& a) const { return x * a.y - y * a.x; }
  double operator^(const point& a) const { return x * a.x + y * a.y; }
} p[MAXN], tp[3];
inline bool dotsInline(const point& p1, const point& p2, const point& p3) {
  return zero((p1 - p3) * (p2 - p3));
}
inline bool parallel(const point& u1, const point& u2, const point& v1,
                     const point& v2) {
  return zero((u1 - u2) * (v1 - v2));
}
inline point intersection(const point& u1, const point& u2, const point& v1,
                          const point& v2) {
  return u1 + (u2 - u1) * (((u1 - v1) * (v1 - v2)) / ((u1 - u2) * (v1 - v2)));
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%lf%lf", &p[i].x, &p[i].y);
    p[i].x += MAXV;
    p[i].y += MAXV;
  }
  p[n] = p[0];
  for (int i = 0; i < n; i++) {
    if (p[i].x < p[i + 1].x) {
      for (int j = p[i].x; j <= p[i + 1].x; j++) {
        tp[0] = point(j, 0);
        tp[1] = point(j, 1);
        if (!parallel(tp[0], tp[1], p[i], p[i + 1])) {
          x[j].push_back(intersection(tp[0], tp[1], p[i], p[i + 1]).y);
        }
      }
    } else if (p[i].x > p[i + 1].x) {
      for (int j = p[i + 1].x; j <= p[i].x; j++) {
        tp[0] = point(j, 0);
        tp[1] = point(j, 1);
        if (!parallel(tp[0], tp[1], p[i], p[i + 1])) {
          x[j].push_back(intersection(tp[0], tp[1], p[i], p[i + 1]).y);
        }
      }
    } else {
      x[int(p[i].x + .2)].push_back(p[i].y);
      x[int(p[i].x + .2)].push_back(p[i + 1].y);
    }
    if (p[i].y < p[i + 1].y) {
      for (int j = p[i].y; j <= p[i + 1].y; j++) {
        tp[0] = point(0, j);
        tp[1] = point(1, j);
        if (!parallel(tp[0], tp[1], p[i], p[i + 1])) {
          y[j].push_back(intersection(tp[0], tp[1], p[i], p[i + 1]).x);
        }
      }
    } else if (p[i].y > p[i + 1].y) {
      for (int j = p[i + 1].y; j <= p[i].y; j++) {
        tp[0] = point(0, j);
        tp[1] = point(1, j);
        if (!parallel(tp[0], tp[1], p[i], p[i + 1])) {
          y[j].push_back(intersection(tp[0], tp[1], p[i], p[i + 1]).x);
        }
      }
    } else {
      y[int(p[i].y + .2)].push_back(p[i].x);
      y[int(p[i].y + .2)].push_back(p[i + 1].x);
    }
  }
  int lowx = MAXV * 2 - 1, highx = 0;
  long long tot = 0;
  for (int i = 0; i < MAXV * 2; i++) {
    if (x[i].size() == 0) continue;
    lowx = min(lowx, i);
    highx = max(highx, i);
    double l = x[i][0], r = x[i][0];
    for (int j = 0; j < (int)x[i].size(); j++) {
      l = min(x[i][j], l);
      r = max(x[i][j], r);
    }
    int L = (int)l - 2, R = (int)r + 2;
    while (sgn(L - l) < 0) L++;
    while (sgn(r - R) < 0) R--;
    cx[i] = R - L + 1;
    tot += cx[i];
  }
  double mul = (2.0 / tot) / (tot - 1);
  int lowy = MAXV * 2 - 1, highy = 0;
  for (int i = 0; i < MAXV * 2; i++) {
    if (y[i].size() == 0) continue;
    lowy = min(lowy, i);
    highy = max(highy, i);
    double l = y[i][0], r = y[i][0];
    for (int j = 0; j < (int)y[i].size(); j++) {
      l = min(y[i][j], l);
      r = max(y[i][j], r);
    }
    int L = (int)l - 2, R = (int)r + 2;
    while (sgn(L - l) < 0) L++;
    while (sgn(r - R) < 0) R--;
    cy[i] = R - L + 1;
  }
  double A = cx[highx], B = cx[highx], C = 0;
  double ans = A * (cx[highx - 1] * mul);
  for (int i = highx - 1; i > lowx; i--) {
    C += 2 * cx[i + 1];
    B += C + cx[i];
    A += B;
    ans += A * (cx[i - 1] * mul);
  }
  A = cy[highy];
  B = cy[highy];
  C = 0;
  ans += A * (cy[highy - 1] * mul);
  for (int i = highy - 1; i > lowy; i--) {
    C += 2 * cy[i + 1];
    B += C + cy[i];
    A += B;
    ans += A * (cy[i - 1] * mul);
  }
  printf("%.20lf\n", ans * .5);
  return 0;
}