poligon

#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

#define OO 10000
struct Point
{
    int x, y;

    friend std::ifstream& operator >> (std::ifstream &flux, Point &p)
    {
        flux >> p.x >> p.y;
        return flux;
    }

    friend std::ofstream& operator << (std::ofstream &flux, Point p)
    {
        flux << "(" << p.x << ", " << p.y << ")";
        return flux;
    }
};

std::ifstream fin ("punctinpoligonsimplu.in");
std::ofstream fout ("punctinpoligonsimplu.out");

Point p0;
int n, m;
std::vector <Point> polygon;

inline bool onSegment (Point p, Point q, Point r)
{
    return (std::min (p.x, r.x) <= q.x && q.x <= std::max (p.x, r.x) &&
            std::min (p.y, r.y) <= q.y && q.y <= std::max (p.y, r.y));
}

inline int orientation (Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (!val) return 0;
    return (val > 0 ? 1 : -1);
}

inline bool doIntersect (Point p1, Point q1, Point p2, Point q2)
{
    int o1 = orientation (p1, q1, p2);
    int o2 = orientation (p1, q1, q2);
    int o3 = orientation (p2, q2, p1);
    int o4 = orientation (p2, q2, q1);

    if (o1 != o2 && o3 != o4) return true;

    if (!o1 && onSegment (p1, p2, q1)) return true;

    if (!o2 && onSegment (p1, q2, q1)) return true;

    if (!o3 && onSegment (p2, p1, q2)) return true;

    if (!o4 && onSegment (p2, q1, q2)) return true;

    return false;
}

inline bool isInside (Point p)
{
    if (n < 3) return false;

    std::vector <bool> Seen (n, false);
    Point extreme = {rand () % 1001 + OO, rand () % 1001 + OO};
    int cnt = 0, i = 0;
    do
    {
        int next = (i + 1) % n;

        if (doIntersect (polygon[i], polygon[next], p, extreme))
        {
            //if (!orientation (polygon[i], p, polygon[next]))
                //return onSegment (polygon[i], p, polygon[next]);
            if (!orientation (polygon[i], p, polygon[next]) && onSegment(polygon[i], p, polygon[next]))
                return true;

            if ((!orientation (p, polygon[i], extreme) && !Seen[i]))
            {
                ++ cnt, Seen[i] = true;
                /*fout << "[";
                fout << polygon[i];
                fout << ", ";
                fout << polygon[next];
                fout << "], ";*/
                goto label;
            }

            if ((!orientation (p, polygon[next], extreme) && !Seen[next]))
            {
                ++ cnt, Seen[next] = true;
                /*fout << "[";
                fout << polygon[i];
                fout << ", ";
                fout << polygon[next];
                fout << "], ";*/
                goto label;
            }

            if (orientation (p, polygon[i], extreme) && orientation (p, polygon[next], extreme))
            {
                ++ cnt;
                /*fout << "[";
                fout << polygon[i];
                fout << ", ";
                fout << polygon[next];
                fout << "], ";*/
            }
        }
        label : i = next;
    } while (i);

    //fout << cnt << " => ";
    return (cnt & 1);
}

int main ()
{
    std::srand (std::time (nullptr));

    fin >> n >> m;

    polygon = std::vector <Point> (n, {0, 0});

    for (int i = 0; i < n; ++ i)
        fin >> polygon[i];

    for ( ; m; -- m)
    {
        Point p;
        fin >> p;
        //fout << p;
        //fout << ": ";
        fout << (isInside (p) ? "DA" : "NU") << "\n";
    }

    return 0;
}