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 <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
using namespace std;
const double EPS = 1e-8;
const double INF = 1e12;
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define X real()
#define Y imag()

typedef complex<double> P;
typedef vector<P> VP;
struct L : array<P, 2>{
    L(const P& a, const P& b){ at(0)=a; at(1)=b; }
    L(){}
};
namespace std{
    bool operator < (const P& a, const P& b){
        return !EQ(a.X,b.X) ? a.X<b.X : a.Y+EPS<b.Y;
    }
    bool operator == (const P& a, const P& b){
        return abs(a-b) < EPS;
    }
}

double dot(P a, P b){
    return (conj(a)*b).X;
}
double cross(P a, P b){
    return (conj(a)*b).Y;
}
int ccw(P a, P b, P c){
    b -= a;
    c -= a;
    if(cross(b,c) > EPS) return +1; //ccw
    if(cross(b,c) < -EPS) return -1; //cw
    if(dot(b,c) < -EPS) return +2; //c-a-b
    if(dot(b,b-c) > EPS) return -2; //a-b-c
    return 0; //a-c-b
}

bool intersectSS(const L& a, const L& b){
    return ( ccw(a[0],a[1],b[0]) *ccw(a[0],a[1],b[1]) <= 0 ) &&
        ( ccw(b[0],b[1],a[0]) *ccw(b[0],b[1],a[1]) <= 0 );
}
bool isParallel(const P &a, const P &b){
    return abs(cross(a,b)) < EPS;
}
bool isParallel(const L &a, const L &b){
    return isParallel(a[1]-a[0], b[1]-b[0]);
}
P crosspointLL(const L &l, const L &m) {
  double A = cross(l[1]-l[0], m[1]-m[0]);
  double B = cross(l[1]-l[0], l[1]-m[0]);
  return m[0] + B/A *(m[1]-m[0]);
}

int main(){
    int n;
    cin >> n;
    VP p(n);
    for(int i=0; i<n; i++){
        int x,y;
        cin >> x >> y;
        p[i] = P(x, y);
    }
    vector<double> area;
    const double dd = 0.5/4;
    for(double x=-1e3; x<1e3+EPS; x+=0.5){
        double len[2] = {0, 0};
        for(int d=0; d<2; d++){
            double xx = x +(1 +2*d)*dd;
            L cut(P(xx, -1e3), P(xx, 1e3));
            VP cp;
            for(int i=0; i<n; i++){
                L edge(p[i], p[(i+1)%n]);
                if(!isParallel(cut, edge) and intersectSS(cut, edge)){
                    cp.push_back(crosspointLL(cut, edge));
                }
            }
            sort(cp.begin(), cp.end());
            for(int i=0; i<(int)cp.size(); i+=2){
                len[d] += abs(cp[i+1] -cp[i]);
            }
        }
        double diff = (len[1]-len[0])/2;
        len[0] -= diff;
        len[1] += diff;
        area.push_back((len[0] +len[1])/4);
    }
    double s[2] = {0, 0};
    for(int i=0; i<(int)area.size(); i++){
        s[i%2] += area[i];
    }
    cout << fixed << setprecision(10);
    cout << max(s[0], s[1]) << endl;
    return 0;
}