Cod sursa(job #788693)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 15 septembrie 2012 16:44:47
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#define NM 810
#define x first
#define y second

using namespace std;

ifstream f("poligon.in");
ofstream g("poligon.out");

typedef pair<int, int> PI;

int N,M,ANS;
int i,j;
PI V[NM],Q;
int A[NM],B[NM],C[NM];
double Slope[NM],C2[NM];
int X[NM],NX;
vector<int> Strip[NM];
bool Online;

inline bool CMP (int a, int b)
{
    return (Slope[a]*(X[i]+X[i+1])+2*C2[a]<Slope[b]*(X[i]+X[i+1])+2*C2[b]);
}

inline bool Check (int i, PI Q)
{
    if (A[i]*Q.x+B[i]*Q.y+C[i]==0) Online=1;
    return (Q.y>=Slope[i]*Q.x+C2[i]);
}

int main ()
{
    f >> N >> M;
    for (i=1; i<=N; i++)
    {
        f >> V[i].x >> V[i].y;
        X[i]=V[i].x;
    }
    V[N+1]=V[1];

    sort(X+1,X+N+1);
    X[NX=1]=X[1];
    for (i=2; i<=N; i++)
        if (X[i]!=X[i-1])
            X[++NX]=X[i];
    X[NX+1]=0;

    for (i=1; i<=N; i++)
    {
        A[i]=V[i+1].y-V[i].y;
        B[i]=V[i].x-V[i+1].x;
        C[i]=-(A[i]*V[i].x+B[i]*V[i].y);
        Slope[i]=-1.0*A[i]/B[i];
        C2[i]=-1.0*C[i]/B[i];
    }

    for (i=1; i<=NX; i++)
    {
        for (j=1; j<=N; j++)
            if (X[i]>=min(V[j].x,V[j+1].x) && X[i]<max(V[j].x,V[j+1].x))
                Strip[i].push_back(j);

        sort(Strip[i].begin(),Strip[i].end(),CMP);
    }

    for (; M>=1; M--)
    {
        f >> Q.x >> Q.y;
        if (Q.x<X[1] || Q.x>X[NX]) continue;
        Online=0;
        int step;
        for (step=1024,i=0; step>0; step>>=1)
            if (i+step<=NX && X[i+step]<Q.x)
                i+=step;
        for (step=1024,j=0; step>0; step>>=1)
            if (j+step<=Strip[i].size() && Check(Strip[i][j+step-1],Q))
                j+=step;
        if (j%2==1 || Online==1)
            ANS++;
    }

    g << ANS << '\n';

    f.close();
    g.close();
    return 0;
}