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 <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

/* ?????¬????´? */
typedef complex<double> Point;
typedef pair<Point, Point> Line;
typedef vector<Point> VP;
const double EPS = 1e-6; // ?¨±?????????^2
const double INF = 1e9;
#define X real()
#define Y imag()
// #define LE(n,m) ((n) < (m) + EPS)
#define LE(n,m) ((n) - (m) < EPS)
// #define GE(n,m) ((n) + EPS > (m))
#define GE(n,m) (EPS > (m) - (n))
#define EQ(n,m) (abs((n)-(m)) < EPS)

// ?????????dot(a,b) = |a||b|cos??
double dot(Point a, Point b) {
  return a.X*b.X + a.Y*b.Y;
}

// ?????????cross(a,b) = |a||b|sin??
double cross(Point a, Point b) {
  return a.X*b.Y - a.Y*b.X;
}

// ??????????????????
int ccw(Point a, Point b, Point c) {
  b -= a;  c -= a;
  if (cross(b,c) >  EPS) return +1;  // counter clockwise
  if (cross(b,c) < -EPS) return -1;  // clockwise
  if (dot(b,c)   < -EPS) return +2;  // c--a--b on line
  if (norm(b) < norm(c)) return -2;  // a--b--c on line or a==b
  return 0;                          // a--c--b on line or a==c or b==c
}

// ??´?????¨??????
bool isecLS(Point a1, Point a2, Point b1, Point b2) {
  return cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS;
}

// 2??´????????????
Point crosspointLL(Point a1, Point a2, Point b1, Point b2) {
  double d1 = cross(b2-b1, b1-a1);
  double d2 = cross(b2-b1, a2-a1);
  if (EQ(d1, 0) && EQ(d2, 0)) return a1;  // same line
  assert(!EQ(d2, 0)); // ???????????????
  return a1 + d1/d2 * (a2-a1);
}

// ????§???¢????¬?????????¢???
double area(const VP& ps) {
  double a = 0;
  rep (i, ps.size()) a += cross(ps[i], ps[(i+1) % ps.size()]);
  return a / 2;
}

using pd = pair<double,double>;

int main()
{
    int n;
    cin >>n;
    vector<int> x(n),y(n);
    rep(i,n) cin >>x[i] >>y[i];

    int minx = 100000;
    rep(i,n) minx = min(minx,x[i]);

    rep(i,n)
    {
        x[i] -= minx;
        x[i] *= 2;
    }

    VP p(n);
    rep(i,n) p[i] = Point(x[i],y[i]);

    double whole = abs(area(p));
    double s = 0;
    for(int i=0; i<=4002; i+=2)
    {
        vector<pd> seg;
        rep(j,n)if(x[j]!=x[(j+1)%n] && isecLS(Point(i,-1001),Point(i,1001),p[j],p[(j+1)%n]) && isecLS(Point(i+1,-1001),Point(i+1,1001),p[j],p[(j+1)%n]))
        {
            seg.pb({crosspointLL(p[j], p[(j+1)%n], Point(i,-1001), Point(i,1001)).Y, crosspointLL(p[j], p[(j+1)%n], Point(i+1,-1001), Point(i+1,1001)).Y});
        }

        sort(all(seg));
        reverse(all(seg));
        int SZ = seg.size();
        assert(SZ%2==0);
        for(int j=0; j<SZ; j+=2)
        {
            double a = seg[j].fi - seg[j+1].fi;
            double b = seg[j].se - seg[j+1].se;
            s += (a+b)/2;
        }

    }

    printf("%.10f\n", max(s,whole-s)/2);
    return 0;
}