Problem: E: Do You Divide It? / Do you want to chop it up?

story

Mr. T has been terribly troubled by the problem of plane figures in programming contests he has participated in in the past, and has had a strong grudge against plane figures ever since.

Above all, I have mixed feelings about polygons drawn on a two-dimensional plane, so when I see a polygon, I can't help but chop it up.

When Mr. T chops a polygon, he covers the polygon with a plate with slits at intervals of 0.5 width parallel to the y-axis, and chops and discards the invisible part with the slits.

However, Mr. T does not like unilateral killing, so in order to leave the buds of recurrence in the polygon, care should be taken to make the total area of ​​the figures remaining after chopping as large as possible.

Let's find the area of ​​the figure that remains after Mr. T chops it.

problem

The two-dimensional plane has an infinite length slit in the y-axis direction, and the visible part and the invisible part are switched every 0.5 in the x-axis direction.

As shown in the figure below, a polygon consisting of N vertices continues to translate in the positive x-axis direction on this plane.

<image>

Output the area of ​​the visible part at the moment when the visible part of the polygon becomes the largest.

Input format

Give N in the first line. In the i-th line of the following N lines, the i-th vertex coordinates (x_i, y_i) in the counterclockwise direction of the polygon are given.

The following can be assumed.

* All inputs are integers
* 3 ≤ N ≤ 100, −10 ^ 3 ≤ x_i, y_i ≤ 10 ^ 3
* Given polygons do not share edges or vertices with anything other than adjacent line segments.
* The three consecutive vertices of a given polygon are not on the same straight line



Output format

Output the visible area in one line at the moment when the visible part of the given polygon becomes the largest. Absolute error and relative error are allowed up to 10 ^ {-5}.

Input example 1


6
0 0
-1 -2
3 -2
2 0
3 2
-1 2


Output example 1


6.000000000

Input example 2


Five
0 0
twenty two
4 -2
4 2
twenty two


Output example 2


6.50000000





Example

Input

6
0 0
-1 -2
3 -2
2 0
3 2
-1 2


Output

6.000000000

Solution (in CPP):

Solution:
#include <algorithm>
#include <iostream>
#include <complex>
#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
using namespace std;
using W = double;
using P = complex<W>;
using L = pair<P,P>;
using C = pair<P,W>;
using Poly = vector<P>;
#define X real()
#define Y imag()
const W EPS = (1e-10), pi = acos(-1);

double dot(P a, P b){ return a.X * b.X + a.Y * b.Y;}
W cross(P a, P b){ return a.X * b.Y - a.Y * b.X;}
P projection(P a, P b){ return dot(a, b)/abs(b)/abs(b)*b;}

//直線aと直線bの交点
P intersection(L a, L b){
  P af = a.first, as = a.second, bf = b.first, bs = b.second;
  return af + cross(bs-bf,af-bf)/(-cross(bs-bf,as-bf)+cross(bs-bf,af-bf))*(as-af);
}

//cがa/bと重なってる時は0を返す
//cがa/bと重なってる時+-2を返して欲しいなら+-2のところのEPSの符号を逆にする
int ccw(P a, P b, P c){
  b -= a; c -= a;
  if(cross(b,c) > EPS) return +1;
  if(cross(b,c) < -EPS) return -1;
  if(dot(b,c) < -EPS) return +2;
  if(norm(b) < norm(c)-EPS) return -2;
  return 0;
}

//凸多角形を直線で切る
//ccwが必要
Poly convex_cut(const Poly &p, L l){
  Poly ret;
  int n = p.size();
  for(int i = 0; i < n; ++i){
    P cur = p[i], nex = p[(i+1)%n], lf = l.first, ls = l.second;
    if(ccw(lf, ls, cur) != -1)
      ret.push_back(cur);
    if((ccw(lf, ls, cur) != -1) ^ (ccw(lf, ls, nex) != -1))
      ret.push_back(intersection(L(cur, nex), l));
  }
  return ret;
}

W area(const Poly &p){
  int n = p.size();
  W s = 0;
  for(int i = 0; i < n; ++i) s += cross(p[i],p[(i+1)%n])/2;
  return s;
}

int main(){
  int N;
  cin >> N;
  Poly pol;
  for(int i = 0; i < N; ++i){
    W x, y;
    cin >> x >> y;
    pol.emplace_back(x,y);
  }
  const W INF = 1e9;
  auto calc = [&](Poly t){
                W ret = 0;
                W l = min({0.0,t[1].X,t[2].X}), r = max({0.0,t[1].X,t[2].X});
                for(W x = l; x < r; x += 1){
                  Poly tt = convex_cut(t,L(P(x+0.5,-INF),P(x+0.5,INF)));
                  ret += area(tt);
                  t = convex_cut(t,L(P(x+1,INF),P(x+1,-INF)));
                }
                return abs(ret);
              };
  W s = 0;
  for(int i = 0; i < N; ++i){
    if(abs(P(0,0)-pol[i]) < EPS) continue;
    if(abs(P(0,0)-pol[(i+1)%N]) < EPS) continue;
    Poly t;
    t.push_back(P(0,0));
    t.push_back(pol[i]);
    t.push_back(pol[(i+1)%N]);
    W ds = calc(t);
    if(area(t) > 0) s += ds;
    else s -= ds;
  }
  W ans = max(s,area(pol)-s);
  printf("%.12f\n",ans);
}