Cod sursa(job #658367)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 8 ianuarie 2012 18:16:46
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.38 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 ()
{
    Segment Null;
    Null.A.x=50, Null.A.y=-100;
    Null.B.x=100, Null.B.y=-100;
    Null.Mid=-100;
    for (int i=1; i<X[0]; ++i)
    {
        for (int j=1; j<=NLines; ++j)
        {
            if (Lines[j].A.x<=X[i] and X[i+1]<=Lines[j].B.x)
            {
                Lines[j].Mid=GetY (Lines[j], (X[i]+X[i+1])/2);
                Strips[i].push_back (Lines[j]);
            }
        }
        Strips[i].push_back (Null);
        sort (Strips[i].begin (), Strips[i].end (), Compare);
    }
}

inline int SearchStrip (int x)
{
    int Strip=0;
    for (int Step=1<<10; Step>0; Step>>=1)
    {
        int i=Strip+Step;
        if (i<X[0] and X[i]<=x)
        {
            Strip=i;
        }
    }
    return Strip;
}

inline long long Det (pii A, pii B, pii C)
{
    return (long long)(B.x-A.x)*(long long)(C.y-A.y)-(long long)(B.y-A.y)*(long long)(C.x-A.x);
}

inline int Sign (pii A, pii B, pii C)
{
    long long DetV=Det (A, B, C);
    if (DetV<0)
    {
        return -1;
    }
    if (DetV>0)
    {
        return 1;
    }
    return 0;
}

inline int SearchLine (int SI, pii Point)
{
    int Line=0;
    for (int Step=1<<10; Step>0; Step>>=1)
    {
        int i=Line+Step;
        if (i<Strips[SI].size () and Sign (Strips[SI][i].A, Point, Strips[SI][i].B)<=0)
        {
            Line=i;
        }
    }
    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%2==1 or Sign (Strips[Strip][Line].A, Point, Strips[Strip][Line].B)==0)
        {
            ++S;
        }
    }
    printf ("%d\n", S);
    return 0;
}