Ksusha and Square

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 ≤ 10⁵) — 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 x _i, y _i (|x _i|, |y _i| ≤ 10⁶) — 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:

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

const int co = 1000010;
const int N = 6*co+10;

long long yN[N], yd[N];
long long bn[42], bd[42];
int pred[N];
int last[2*co+10];
int x[100010], y[100010];
int m;

void add(int xa, int ya, int xb, int yb) {
if (xa == xb) return;
if (xa > xb) {
int tmp = xa; xa = xb; xb = tmp;
tmp = ya; ya = yb; yb = tmp;
}
for (int xx=xa;xx<=xb;xx++) {
    m++;
    yN[m] = (long long)ya*(xb-xa) + (long long)(yb-ya)*(xx-xa);
    yd[m] = xb-xa;
    pred[m] = last[xx+co];
    last[xx+co] = m;
  }
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i=0;i<n;i++) scanf("%d %d", x+i, y+i);
  double ans = 0.0;
  for (int r=0;r<2;r++) {
    x[n] = x[0]; y[n] = y[0];
    m = 0;
    for (int i=0;i<=2*co;i++) last[i] = 0;
    for (int i=0;i<n;i++) add(x[i], y[i], x[i+1], y[i+1]);
    double sum = 0, sq = 0, cnt = 0;
    for (int xx=-co;xx<=co;xx++) {
      int k = 0;
      int j = last[xx+co];
      while (j > 0) {
bn[k] = yN[j];
bd[k] = yd[j];
k++;
j = pred[j];
}
if (k == 0) continue;
for (int i=0;i<k;i++)
        for (int j=i+1;j<k;j++)
          if (bn[i]*bd[j] > bn[j]*bd[i]) {
long long tmp = bn[i]; bn[i] = bn[j]; bn[j] = tmp;
tmp = bd[i]; bd[i] = bd[j]; bd[j] = tmp;
}
long long up = bn[k-1]/bd[k-1];
while (up*bd[k-1] > bn[k-1]) up--;
while ((up+1)*bd[k-1] <= bn[k-1]) up++;
      long long down = bn[0]/bd[0];
      while (down*bd[0] < bn[0]) down++;
      while ((down-1)*bd[0] >= bn[0]) down--;
cnt += 1.0*(up-down+1);
sum += 1.0*xx*(up-down+1);
sq += 1.0*xx*xx*(up-down+1);
}
ans += (sq-sum*sum/cnt)/(cnt-1);
for (int i=0;i<n;i++) {
      int tmp = x[i];
      x[i] = y[i];
      y[i] = tmp;
    }
  }
  printf("%.17lf\n", ans);
  return 0;
}