Cod sursa(job #1214309)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 30 iulie 2014 00:39:49
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.72 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<bitset>

using namespace std;

typedef pair<double,int> PDI;
const int NMAX = 800+5;
const int MMAX = 60000+6;
const int INF = (1<<30);

ifstream fin("poligon.in");
ofstream fout("poligon.out");

int N,M,cnt,sol;
int X[NMAX];
int Y[NMAX];
double m[NMAX];
double n[NMAX];
int Rx1[NMAX];
int Rx2[NMAX];
bitset<MMAX> verif;
vector<PDI> R[NMAX];
vector<int> abscise;
vector<int> verticalSides;

inline void calculPanta(int i)
{
    if(X[i]-X[i+1])
    {
        m[i]=(1.0*Y[i]-Y[i+1])/(1.0*X[i]-X[i+1]);
        n[i]=Y[i]-m[i]*X[i];
    }
    else
    {
        m[i]=1.0*INF;
        n[i]=1.0*X[i];
    }
}

inline bool intersection(int a,int b,int c,int d) // [a,b) ^ [c,d)
{
    if(a>b) swap(a,b);
    if(c>d) swap(c,d);
    return max(a,c)<=min(b-1,d-1);
}

inline void insertSideInRegion(int region,int side)
{
    if(m[side]==INF) return;
    double y;
    y=((m[side]*Rx1[region]+n[side])+(m[side]*Rx2[region]+n[side]))/2.0;
    R[region].push_back(make_pair(y,side));
}

inline bool cmp(int x,int y)
{
    return n[x]<n[y];
}

inline int crossProd(int Ax,int Ay,int Bx,int By,int Cx,int Cy)
{
    if(Ax>Bx)
    {
        swap(Ax,Bx);
        swap(Ay,By);
    }
    if ((Ax-Cx)*(By-Cy)-(Ay-Cy)*(Bx-Cx)>0) return 1;
    else if ((Ax-Cx)*(By-Cy)-(Ay-Cy)*(Bx-Cx)<0) return -1;
    else return 0;
}

inline int searchInRegions(int x,int y)
{
    int lo,hi,mi;

    lo=1,hi=cnt;

    while(lo<=hi)
    {
        mi=(lo+hi)/2;
        if(Rx1[mi]<=x && x<=Rx2[mi]) break;
        if(Rx1[mi]>x) hi=mi-1;
        if(Rx2[mi]<x) lo=mi+1;
    }

    if(lo>hi) return 0;

    int r=mi,s,val,pssy=0;

    lo=0,hi=R[r].size()-1;

    while(lo<=hi)
    {
        mi=(lo+hi)/2;
        s=R[r][mi].second;
        val=crossProd(X[s],Y[s],X[s+1],Y[s+1],x,y);
        if(val>0)
        {
            lo=mi+1;
            pssy=max(pssy,mi+1);
        }
        if(val<0) hi=mi-1;
        if(val==0) return 1;
    }

    return (pssy%2);
}

int searchInVerticalSides(int x,int y)
{
    int lo=0,hi=verticalSides.size()-1,mi,s,i;

    while(lo<=hi)
    {
        mi=(lo+hi)/2;
        s=verticalSides[mi];
        if(X[s]==x)
        {
            for(i=mi; i>=0; i--)
            {
                s=verticalSides[i];
                if((Y[s]<=y && y<=Y[s+1]) || (Y[s+1]<=y && y<=Y[s])) return 1;
            }
            for(i=mi; i<verticalSides.size(); i++)
            {
                s=verticalSides[i];
                if((Y[s]<=y && y<=Y[s+1]) || (Y[s+1]<=y && y<=Y[s])) return 1;
            }
            return 0;
        }
        if(X[s]<x) lo=mi+1;
        if(X[s]>x) hi=mi-1;
    }

    return 0;
}

int main()
{
    int i,j,x,y,ok;

    fin>>N>>M;

    for(i=1; i<=N; i++)
    {
        fin>>X[i]>>Y[i];
        if(verif[X[i]]) continue;
        verif[X[i]]=1;
        abscise.push_back(X[i]);
    }

    X[N+1]=X[1];
    Y[N+1]=Y[1];

    for(i=1; i<=N; i++)
    {
        calculPanta(i);
        if(m[i]==INF) verticalSides.push_back(i);
    }

    sort(verticalSides.begin(),verticalSides.end(),cmp);
    sort(abscise.begin(),abscise.end());

    for(i=0; i<abscise.size()-1; i++)
    {
        ++cnt;
        Rx1[cnt]=abscise[i];
        Rx2[cnt]=abscise[i+1];
        for(j=1; j<=N; j++)
            if(intersection(X[j],X[j+1],abscise[i],abscise[i+1])) insertSideInRegion(cnt,j);
        sort(R[cnt].begin(),R[cnt].end());
    }

    while(M--)
    {
        fin>>x>>y;

        ok=searchInRegions(x,y);
        if(!ok) ok=searchInVerticalSides(x,y);

        sol+=ok;
    }

    fout<<sol<<'\n';

    return 0;
}