Cod sursa(job #658362)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 8 ianuarie 2012 18:00:26
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define Infinity 2000000000
#define NMax 805
#define x first
#define y second
#define pii pair <int, int>

using namespace std;

struct Segment
{
    pii A, B;
    double Mid;
};

pii P[NMax];
Segment Lines[NMax];
vector <Segment> Strips[NMax];
int N, M, X[NMax], NLines, S;

void Read ()
{
    scanf ("%d %d", &N, &M);
    vector <int> V;
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d %d", &P[i].x, &P[i].y);
        V.push_back (P[i].x);
    }
    P[N+1]=P[1];
    sort (V.begin (), V.end ());
    X[++X[0]]=V[0];
    for (unsigned i=1; i<V.size (); ++i)
    {
        if (V[i]!=V[i-1])
        {
            X[++X[0]]=V[i];
        }
    }
    X[X[0]+1]=Infinity;
    for (int i=1; i<=N; ++i)
    {
        if (P[i].x==P[i+1].x)
        {
            continue;
        }
        Lines[++NLines].A=P[i], Lines[NLines].B=P[i+1];
        if (P[i].x>P[i+1].x)
        {
            swap (Lines[NLines].A, Lines[NLines].B);
        }
    }
}

inline bool Compare (Segment A, Segment B)
{
    return A.Mid<B.Mid;
}

inline double GetY (Segment L, double x)
{
    double x1=L.A.x;
    double y1=L.A.y;
    double x2=L.B.x;
    double y2=L.B.y;
    return y2-(x2-x)*(y2-y1)/(x2-x1);
}

void BuildStrips ()
{
    for (int i=1; i<X[0]; ++i)
    {
        for (int j=1; j<=NLines; ++j)
        {
            if (X[i]<=Lines[j].A.x and Lines[j].B.x<=X[i+1])
            {
                Lines[j].Mid=GetY (Lines[j], (X[i]+X[i+1])/2);
                Strips[i].push_back (Lines[j]);
            }
        }
        sort (Strips[i].begin (), Strips[i].end (), Compare);
    }
}

inline int SearchStrip (int x)
{
    int L=1, R=X[0]-1, Strip=0;
    while (L<=R)
    {
        int Mid=L+(R-L)/2;
        if (x<=X[Mid+1])
        {
            Strip=Mid;
            L=Mid+1;
        }
        else
        {
            R=Mid-1;
        }
    }
    return Strip;
}

inline int Sign (pii A, pii B, pii C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-A.y*B.x-A.x*C.y;
}

inline int SearchLine (int SI, pii Point)
{
    int L=0, R=Strips[SI].size ()-1, Line=0;
    while (L<=R)
    {
        int Mid=L+(R-L)/2;
        if (Sign (Strips[SI][Mid].A, Strips[SI][Mid].B, Point)>=0)
        {
            Line=Mid;
            L=Mid+1;
        }
        else
        {
            R=Mid-1;
        }
    }
    return Line;
}

int main()
{
    freopen ("poligon.in", "r", stdin);
    freopen ("poligon.out", "w", stdout);
    Read ();
    BuildStrips ();
    for (; M>0; --M)
    {
        pii Point;
        scanf ("%d %d", &Point.x, &Point.y);
        if (Point.x<X[1] or Point.x>X[X[0]])
        {
            continue;
        }
        int Strip=SearchStrip (Point.x);
        int Line=SearchLine (Strip, Point);
        if (Sign (Strips[Strip][Line].A, Strips[Strip][Line].B, Point)<0)
        {
            continue;
        }
        if ((Line+1)%2==1 or Sign (Strips[Strip][Line].A, Strips[Strip][Line].B, Point)==0)
        {
            ++S;
        }
    }
    printf ("%d\n", S);
    return 0;
}