PunctInPoligonSimplu

#include <cstdio>
#include <vector>
#include <algorithm>

#define nmax 805
#define y first
#define x second
#define y1 first
#define y2 second
#define mp make_pair

using namespace std;

typedef pair <int, int> ii;
typedef pair <float, int> interval;

int n, m, nintr, nrsegm [nmax];
ii p [nmax], p2 [nmax];
ii intr [nmax];
interval segm [nmax] [nmax];

void scan ()
{
    int i;
    scanf ("%d%d", &n, &m);
    for (i=1; i <= n; ++i)
    {
        scanf ("%d%d", &p [i].x, &p [i].y);
        p2 [i]=p [i];
    }
}

inline float xmijloc (int p1, int p2, int k)
{
    float mx, p1x, p2x, p1y, p2y;
    int aux;
    if (p [p1].y > p [p2].y)
    {
        aux=p1;
        p1=p2;
        p2=aux;
    }
    p1y=p [p1].y;
    p2y=p [p2].y;
    if (p1y < intr [k].y1)
        p1y=intr [k].y1;
    if (p2y > intr [k].y2)
        p2y=intr [k].y2;
    int a=p [p1].y-p [p2].y, b=p [p2].x-p [p1].x, c=p [p1].x*p [p2].y - p [p1].y*p [p2].x;
    //long long a=p [p1].y-p [p2].y, b=p [p2].x-p [p1].x, c=(long long)p [p1].x*p [p2].y - (long long)p [p1].y*p [p2].x;
    p1x=(float)(-b*p1y-c)/a;
    p2x=(float)(-b*p2y-c)/a;
    mx=(p1x + p2x)/2;
    return mx;
}

void bucatele ()
{
    int i, j;
    ii a1, a2, aux;
    sort (p2+1, p2+1+n);
    p [n+1]=p [1];
    i=2;
    for (; i < n && p2 [i].y == p2 [i-1].y; ++i);
    --i;
    for (; i < n; ++i)
    {
        j=i+1;
        while (j < n && p2 [j+1].y == p2 [j].y)
            ++j;
        intr [++nintr]=ii (p2 [i].y, p2 [j].y);
        i=j-1;
    }
    for (i=1; i <= nintr; ++i)
    {
        for (j=1; j <= n; ++j)
        {
            a1=p [j];
            a2=p [j+1];
            if ((a1.y > a2.y) || (a1.y == a2.y && a1.x > a2.x))
            {
                aux=a1;
                a1=a2;
                a2=aux;
            }
            if (a1.y >= intr [i].y2) continue;
            if (a2.y <= intr [i].y1) continue;
            segm [i] [++nrsegm [i]]= (mp (xmijloc (j, j+1, i), j));
        }
        sort (segm [i]+1, segm [i]+1+nrsegm [i]);
    }
}

inline bool exista (ii punct)
{
    int s=1<<10, i;
    for (i=0; s; s >>= 1)
    {
        if (n < i+s) continue;
        if (punct.y < p2 [i+s].y) continue;
        if (punct.y == p2 [i+s].y && punct.x < p2 [i+s].x) continue;
        i+=s;
    }
    if (i == 0) return false;
    if (p2 [i] == punct) return true;
    return false;
}

inline int semn (ii punct, int ind)
{
    ii p1, p2;
    if (p [ind].y > p [ind+1].y)
    {
        p1=p [ind+1];
        p2=p [ind];
    }
    else
    {
        p1=p [ind];
        p2=p [ind+1];
    }
    //long long a=p1.y-p2.y, b=p2.x-p1.x, c=(long long)p1.x*p2.y - (long long)p1.y*p2.x;
    int a=p1.y-p2.y, b=p2.x-p1.x, c=p1.x*p2.y - p1.y*p2.x;
    return a*punct.x+b*punct.y+c;
}

int cb1 (int yy)
{
    int s=1<<10, i;
    for (i=0; s; s >>= 1)
        if (nintr >= i+s && intr [i+s].y1 <= yy)
            i+=s;
    return i;
}

int cb2 (ii punct, int k)
{
    if (semn (punct, segm [k] [1].second) > 0) return 0;
    if (semn (punct, segm [k] [nrsegm [k]].second) < 0) return 0;
    int s=1<<10, i;
    for (i=0; s; s >>= 1)
    {
        if (nrsegm [k] < i+s) continue;
        if (semn (punct, segm [k] [i+s].second) <= 0)
            i+=s;
    }
    if (semn (punct, segm [k] [i+s].second) == 0) return 1;
    return i;
}

inline bool interior (ii punct)
{
    if (punct.y < intr [1].y1 || punct.y > intr [nintr].y2) return false;
    if (exista (punct))
        return true;
    int k=cb1 (punct.y);
    if (cb2 (punct, k) % 2 == 1)
        return true;
    if (punct.y == intr [k].y1 && k != 1)
        if (cb2 (punct, k-1) % 2 == 1)
            return true;
    return false;
}

int rez ()
{
    int i, num=0;
    ii punct;
    for (i=1; i <= m; ++i)
    {
        scanf ("%d%d", &punct.x, &punct.y);
        if (interior (punct))
            printf("DA\n");
        else
            printf("NU\n");
    }
    return num;
}

int main ()
{
    freopen ("punctinpoligonsimplu.in", "r", stdin);
    freopen ("punctinpoligonsimplu.out", "w", stdout);
    scan ();
    bucatele ();
    rez ();
    return 0;
}