Cod sursa(job #712934)

Utilizator rootsroots1 roots Data 13 martie 2012 22:25:51
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>

#define maxN 801

using namespace std;

struct punct
{
    long long x,y;
}P[maxN];

struct dreapta
{
    double a,b,c;
    long long xA,xB;
}D[maxN];

struct segment
{
    double xA,yA,xB,yB;
}S[maxN][maxN];

inline bool cmpPunct(punct a,punct b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}

inline bool cmpSegment(segment a,segment b)
{
    return a.yA+a.yB<b.yA+b.yB;
}

int ab[maxN];
int cntS[maxN];

inline int bsFasie(int x,int L,int R)
{
    if(L<R)
    {
        int M=(R-L)/2+L;

        if(ab[M]>=x) return bsFasie(x,L,M);
        else return bsFasie(x,M+1,R);
    }
    if(ab[L]!=x) return L-1;
    return L;
}

inline int bsSegmente(int x,int lev,int L,int R)
{
    if(L<R)
    {
        int M=(R-L)/2+L;

        if(S[lev][M].yA+S[lev][M].yB>=x) return bsSegmente(x,lev,L,M);
        else return bsSegmente(x,lev,M+1,R);
    }
    if(S[lev][L].yA+S[lev][L].yB<x&&L==cntS[lev]) return -1;
    if(S[lev][L].yA+S[lev][L].yB!=x&&L!=1) return L-1;
    return L;
}

int main()
{
    int M,N,x,y;

    freopen("poligon.in","r",stdin);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;++i) scanf("%lld%lld",&P[i].x,&P[i].y);

    P[0]=P[N];
    for(int i=0;i<N;++i)
    {
        D[i].a=P[i].y-P[i+1].y;
        D[i].b=P[i+1].x-P[i].x;
        D[i].c=P[i].x*P[i+1].y-P[i+1].x*P[i].y;

        D[i].xA=P[i].x;
        D[i].xB=P[i+1].x;
        if(D[i].xA>D[i].xB)
        {
            D[i].xA^=D[i].xB;
            D[i].xB^=D[i].xA;
            D[i].xA^=D[i].xB;
        }
    }

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

    ab[0]=0;
    ab[++ab[0]]=P[1].x;
    for(int i=2;i<=N;++i)
        if(P[i].x!=ab[ab[0]]) ab[++ab[0]]=P[i].x;

    for(int i=1;i<ab[0];++i)
    {
        cntS[i]=0;
        for(int j=0;j<N;++j)
            if(D[j].b&&D[j].xA<=ab[i]&&ab[i+1]<=D[j].xB)
            {
                S[i][++cntS[i]].xA=ab[i];
                S[i][cntS[i]].yA=-(D[j].a*ab[i]+D[j].c)/D[j].b;
                S[i][cntS[i]].xB=ab[i+1];
                S[i][cntS[i]].yB=-(D[j].a*ab[i+1]+D[j].c)/D[j].b;
            }
        sort(S[i]+1,S[i]+cntS[i]+1,cmpSegment);
    }

    freopen("poligon.out","w",stdout);

    int count=0;
    for(;M--;)
    {
        scanf("%d%d",&x,&y);

        if(x<ab[1]||ab[ab[0]]<x) continue;
        int pos=bsFasie(x,1,ab[0]);
        if(pos==ab[0]) --pos;

        pos=bsSegmente(2*y,pos,1,cntS[pos]);
        if(pos==-1) continue;
        if(pos&1) ++count;
    }

    printf("%d\n",count);

    return 0;
}