Cod sursa(job #788681)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 15 septembrie 2012 16:11:12
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.38 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];
int X[NM],NX;
vector<int> Strip[NM];
bool Online;

inline bool CMP (int a, int b)
{
    double y1,y2;
    y1=( (1.0*C[a]-A[a]*X[i])/B[a]+(1.0*C[a]-A[a]*X[i+1])/B[a] )/2;
    y2=( (1.0*C[b]-A[b]*X[i])/B[b]+(1.0*C[b]-A[b]*X[i+1])/B[b] )/2;
    return y1<y2;
}

inline int SearchStrip (int x)
{
    int P=1,M,U=NX,ANS=NX;

    while (P<=U)
    {
        M=(P+U)/2;
        if (x>=X[M])
        {
            ANS=M;
            U=M-1;
        }
        else
            P=M+1;
    }

    return ANS;
}

inline int Sign (int i, int j, const PI& P3)
{
    if (i>j) swap(i,j);
    PI P1=V[i];
    PI P2=V[j];
    int S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
    if (S==0) return 0;
    return (S<0?-1:1);
}

inline int SearchLine (const PI& Q)
{
    int P=0,U=Strip[i].size()-1,M,ANS=0;

    while (P<=U)
    {
        M=(P+U)/2;

        if (Sign(Strip[i][M],Strip[i][M]+1,Q)<=0)
        {
            if (Sign(Strip[i][M],Strip[i][M]+1,Q)==0) Online=1;
            ANS=M;
            P=M+1;
        }
        else
            U=M-1;
    }

    return ANS;
}

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];
    X[0]=-1;
    for (i=2; i<=N; i++)
        if (X[i]!=X[i-1])
            X[++NX]=X[i];

    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;
    }

    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;
        i=SearchStrip(Q.x);
        j=SearchLine(Q);
        if (j%2==1 || Online==1)
            ANS++;
    }

    g << ANS << '\n';

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