Cod sursa(job #1211168)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 22 iulie 2014 04:10:51
Problema Poligon Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.68 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cstdio>

using namespace std;

const int NMAX = 800+5;
const int MMAX = 60000+6;
const int INF = (1<<30);

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

struct point
{
    double x,y;
    int i;

    point()
    {

    }

    point(double _x,double _y,int _i)
    {
        x=_x;
        y=_y;
        i=_i;
    }

    inline bool operator()(const point &A,const point &B)
    {
        return A.x<B.x;
    }
};

inline int crossProd(point A,point B,point C)
{
    return (A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x);
}

struct side
{
    point A,B,M;
    int i;
    double m,n;

    side()
    {

    }

    side(point _A,point _B,int _i)
    {
        A=_A;
        B=_B;
        i=_i;
        if(A.x-B.x)
        {
            m=(A.y-B.y)/(A.x-B.x);
            n=A.y-m*A.x;
            if(A.x>B.x) swap(A,B);
        }
        else
        {
            m=INF;
            n=A.x;
            if(A.y>B.y) swap(A,B);
        }
        M.x=(A.x+B.x)/2.0;
        M.y=(A.y+B.y)/2.0;

    }

    point pointOnSide(double x)
    {
        return point(x,m*x+n,-1);
    }

    inline bool operator()(const side &AB,const side &MN)
    {
        if(AB.m==INF && MN.m==INF) return AB.n<MN.n;
        if(AB.m==INF || MN.m==INF) return 0;
        return AB.M.y<MN.M.y;
    }

    inline bool pointOn(point X)
    {
        if(m==INF)
        {
            if(X.x==n) return X.y>=A.y && X.y<=B.y;
            return 0;
        }
        if(A.x<=X.x && X.x<=B.x) return crossProd(A,B,X)==0;
        return 0;
    }
};

struct region
{
    int x,y;
    vector<side> V;

    region()
    {

    }

    region(int _x,int _y)
    {
        x=_x;
        y=_y;
        V.resize(0);
    }

    inline void add(side AB)
    {
        if(AB.m==INF) return;
        side MN(AB.pointOnSide(x),AB.pointOnSide(y),AB.i);
        V.push_back(MN);
    }

    inline void sortSides()
    {
        sort(V.begin(),V.end(),side());
    }
};

int N,M,cnt,sol;
point P[NMAX];
side S[NMAX];
vector<side> verticalSides;
region R[NMAX];

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

inline void increaseSolution()
{
    sol++;
}

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

    fin>>N>>M;

    for(i=1; i<=N; i++)
    {
        fin>>x>>y;
        P[i]=point(x,y,i);
    }

    P[N+1]=P[1];

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

    sort(verticalSides.begin(),verticalSides.end(),side());

    sort(P+1,P+N+1,point());

    for(j=1,i=2; i<=N; i++)
    {
        if(P[i-1].x!=P[i].x)
        {
            R[++cnt]=region(P[j].x,P[i].x);
            for(k=1; k<=N; k++)
                if(intersection(S[k].A.x,S[k].B.x,P[j].x,P[i].x)) R[cnt].add(S[k]);
            j=i;
            R[cnt].sortSides();
            continue;
        }
    }

    int lo,hi,mi,pssy;
    region Z;

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

        lo=1,hi=cnt;

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

        if(lo<=hi)
        {
            Z=R[mi];
            lo=0,hi=Z.V.size()-1;

            pssy=0;

            while(lo<=hi)
            {
                mi=(lo+hi)/2;
                if(crossProd(Z.V[mi].A,Z.V[mi].B,point(x,y,-1))>0)
                {
                    pssy=max(pssy,mi+1);
                    lo=mi+1;
                }
                else hi=mi-1;
                if(crossProd(Z.V[mi].A,Z.V[mi].B,point(x,y,-1))==0)
                {
                    pssy=1;
                    break;
                }
            }

            if(pssy%2) increaseSolution();

            continue;
        }

        continue;

        lo=0,hi=verticalSides.size()-1;
        i=hi,j=lo;

        while(lo<=hi)
        {
            mi=(lo+hi)/2;
            if(verticalSides[mi].n==x)
            {
                for(i=mi; i>=lo && verticalSides[i-1].n==x; i--);
                for(j=mi; j<=hi && verticalSides[j+1].n==x; j++);
                break;
            }
            if(verticalSides[mi].n<x) lo=mi+1;
            if(verticalSides[mi].n>x) hi=mi-1;
        }

        for(k=i; k<=j; k++)
            if(verticalSides[k].pointOn(point(x,y,-1)))
            {
                increaseSolution();
                break;
            }
    }

    fout<<sol<<'\n';

    return 0;
}