題目來(lái)源：http:///group/aUVPeyEnI2/contest/229510
時(shí)間限制：2s
空間限制：256MB
題目大意：
給定一個(gè)凸多邊形，有一種連接兩個(gè)頂點(diǎn)可以將多邊形分成兩個(gè)非空的面積為整數(shù)的圖形，詢問(wèn)這種線有多少條。
數(shù)據(jù)范圍：
4 ≤ n ≤ 200 000
?109 ≤ xi, yi ≤ 109
樣例：


代碼：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <complex>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);  i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pi acos(-1.0)
#define mem0(a) memset(a,0,sizeof(a))
#define memf(b) memset(b,false,sizeof(b))
#define maxn 401010
int x[maxn],y[maxn];
int va[maxn],pre[maxn],p[maxn][3][3][3];
int across(int a,int b,int c,int d)
{
    return a*d-b*c;
}
int main()
{
    freopen("integral.in","r",stdin);
    freopen("integral.out","w",stdout);
    mem0(p);
    mem0(pre);
    int n;
    cin>>n;
    rep(i,1,n 1)
    {
        cin>>x[i]>>y[i];
        x[i]=x[i]&1;
        y[i]=y[i]&1;
        x[i n]=x[i];
        y[i n]=y[i];
    }
    rep(i,1,n<<1|1)
    {
        va[i]=across(x[i-1],y[i-1],x[i],y[i]);
        pre[i]=pre[i-1] va[i];
    }
    if(pre[n 1]&1)
    {
        cout<<"0"<<endl;
        return 0;
    }
//  rep(i,1,n<<1|1)
//  {
//      printf("]",x[i]);
//  }
//  cout<<endl;
//  rep(i,1,n<<1|1)
//  {
//      printf("]",y[i]);
//  }
//  cout<<endl;
//  rep(i,1,n<<1|1)
//  {
//      printf("]",pre[i]);
//  }
//  cout<<endl;
    rep(i,1,n<<1|1)rep(a,0,2)rep(b,0,2)rep(c,0,2)
    {
        if(x[i]==a&&y[i]==b&&(pre[i]&1)==c)
        p[i][a][b][c]=p[i-1][a][b][c] 1;
        else
        p[i][a][b][c]=p[i-1][a][b][c];
    }
//  cout<<endl;
//  rep(i,1,n 1)
//  {
//      rep(a,0,2)
//      rep(b,0,2)
//      rep(c,0,2)
//      {
//          printf("]",p[i][a][b][c]);
//      }
//      cout<<endl;
//  }
//  cout<<endl;
    ll ans=0;
    rep(i,1,n 1)
    {
        int l=i 2,r=n i-2;
        rep(a,0,2)rep(b,0,2)rep(c,0,2)
        {
            int t=((x[i]*b-y[i]*a c-pre[i])&1);
            if(t==0)ans =p[r][a][b][c]-p[l-1][a][b][c];
//          printf("]",ans);
        }
//      cout<<endl;
    }
    
    cout<<ans/2<<endl;
    return 0;
}