Геометрия в double

#include <bits/stdc++.h>
using namespace std;
using double_type = long double;
#define ulong uint64_t
#define long int64_t
#define double double_type
#define all(x) begin(x), end(x)

const double EPS = 1e-9;

bool double_equal(double a, double b) {
    return fabs(a - b) <= EPS;
}

bool double_less(double a, double b) {
    return a < b - EPS;
}

bool double_greater(double a, double b) {
    return a > b + EPS;
}

struct Vector {
    double x, y;

    Vector(double a, double b) :
        x(a),
        y(b) {}

    Vector() :
        Vector(0, 0) {}

    friend bool operator==(Vector a, Vector b) {
        return double_equal(a.x, b.x) && double_equal(a.y, b.y);
    }

    friend bool operator!=(Vector a, Vector b) {
        return !(a == b);
    }

    friend Vector vec(Vector a, Vector b) {
        return {b.x - a.x, b.y - a.y};
    }

    friend Vector operator+(Vector a, Vector b) {
        return {a.x + b.x, a.y + b.y};
    }

    friend Vector operator-(Vector a, Vector b) {
        return {a.x - b.x, a.y - b.y};
    }

    friend Vector operator-(Vector a) {
        return {-a.x, -a.y};
    }

    friend Vector operator*(Vector a, double k) {
        return {a.x * k, a.y * k};
    }

    friend Vector operator/(Vector a, double k) {
        return {a.x / k, a.y / k};
    }

    void operator+=(Vector b) {
        x += b.x;
        y += b.y;
    }

    void operator-=(Vector b) {
        x -= b.x;
        y -= b.y;
    }

    void operator*=(double k) {
        x *= k;
        y *= k;
    }

    void operator/=(double k) {
        x /= k;
        y /= k;
    }

    friend double cross_prod(Vector a, Vector b) {
        return a.x * b.y - a.y * b.x;
    }

    friend double dot_prod(Vector a, Vector b) {
        return a.x * b.x + a.y * b.y;
    }

    double len2() {
        return x * x + y * y;
    }

    double len() {
        return sqrt(len2());
    }

    friend double dist2(Vector a, Vector b) {
        return vec(a, b).len2();
    }

    friend double dist(Vector a, Vector b) {
        return vec(a, b).len();
    }
};

const Vector NONE(rand(), rand());
const Vector MANY(rand(), rand());

istream &operator>>(istream &in, Vector &v) {
    return in >> v.x >> v.y;
}

ostream &operator<<(ostream &out, Vector v) {
    if (v == NONE) {
        return out << "NONE";
    } else if (v == MANY) {
        return out << "MANY";
    } else {
        return out << v.x << ' ' << v.y;
    }
}

struct Line {
    Vector first, second;

    Line(Vector a, Vector b) :
        first(a),
        second(b) {
        assert(first != second);
    }

    Line() :
        Line({0, 0}, {1, 0}) {}

    bool have(Vector p) {
        return double_equal(cross_prod(vec(first, p), vec(first, second)), 0);
    }
};

ostream &operator<<(ostream &out, Line l) {
    return out << "line " << l.first << ", " << l.second;
}

struct Ray {
    Vector first, second;

    Ray(Vector a, Vector b) :
        first(a),
        second(b) {
        assert(first != second);
    }

    Ray() :
        Ray({0, 0}, {1, 0}) {}

    bool have(Vector p) {
        return double_equal(cross_prod(vec(first, p), vec(first, second)), 0)
            && !double_less(dot_prod(vec(first, p), vec(first, second)), 0);
    }
};

ostream &operator<<(ostream &out, Ray r) {
    return out << "ray " << r.first << ", " << r.second;
}

struct Segment {
    Vector first, second;

    Segment(Vector a, Vector b) :
        first(a),
        second(b) {
    }

    Segment() :
        Segment({0, 0}, {0, 0}) {}

    bool have(Vector p) {
        return double_equal(cross_prod(vec(first, p), vec(first, second)), 0)
            && !double_greater(dot_prod(vec(p, first), vec(p, second)), 0);
    }
};

ostream &operator<<(ostream &out, Segment s) {
    return out << "segment " << s.first << ", " << s.second;
}

Vector intersect(Line ab, Line cd) {
    double acd = cross_prod(vec(ab.first, cd.first), vec(ab.first, cd.second));
    double bdc = cross_prod(vec(ab.second, cd.second), vec(ab.second, cd.first));
    if (double_equal(acd + bdc, 0)) {
        return double_equal(acd, 0) ? MANY : NONE;
    } else {
        return ab.first + vec(ab.first, ab.second) * (acd / (acd + bdc));
    }
}

template<class A, class B>
Vector intersect_template(A a, B b) {
    Line x(a.first, a.second);
    Line y(b.first, b.second);
    Vector p = intersect(x, y);
    assert(p != MANY);
    return (a.have(p) && b.have(p)) ? p : NONE;
}

struct Polygon {
    vector<Vector> points;

    Polygon() {}

    Polygon(int n) :
        points(n) {}

    Vector operator[](int i) const {
        assert(0 <= i);
        return points[i % points.size()];
    }

    Vector &operator[](int i) {
        assert(0 <= i);
        return points[i % points.size()];
    }

    bool have(Vector v) {
        for (int i = 0; i + 1 < (int)points.size(); ++i) {
            if (Segment(points[i], points[i + 1]).have(v)) {
                return true;
            }
        }
        if (Segment(points.back(), points.front()).have(v)) {
            return true;
        }
        const double OVER = 1.5e9;
        Ray r(v, v + Vector(OVER, 1));
        int cnt = 0;
        for (int i = 0; i + 1 < (int)points.size(); ++i) {
            cnt += intersect_template(Segment(points[i], points[i + 1]), r) != NONE;
        }
        cnt += intersect_template(Segment(points.back(), points.front()), r) != NONE;
        return cnt % 2;
    }

    friend ostream &operator<<(ostream &out, const Polygon &p) {
        for (Vector v : p.points) {
            out << v << '\n';
        }
        return out;
    }

    friend istream &operator>>(istream &in, Polygon &p) {
        int n;
        in >> n;
        p.points.resize(n);
        for (int i = 0; i < n; ++i) {
            in >> p.points[i];
        }
        return in;
    }
};



double sign_of_turn(Vector a, Vector b, Vector c) {
    return cross_prod(vec(a, b), vec(a, c));
}

bool left_turn(Vector a, Vector b, Vector c) {
    return double_greater(sign_of_turn(a, b, c), 0);
}

bool right_turn(Vector a, Vector b, Vector c) {
    return double_less(sign_of_turn(a, b, c), 0);
}

struct Convex_Polygon : Polygon {
    vector<Vector> points;

    Convex_Polygon() {}

    bool check_ccw() {
        bool result = true;
        int n = (int)points.size();
        for (int i = 0; i + 2 < n; ++i) {
            result &= double_greater(sign_of_turn(points[i], points[i + 1], points[i + 2]), 0);
        }
        result &= double_greater(sign_of_turn(points[n - 2], points[n - 1], points[0]), 0);
        result &= double_greater(sign_of_turn(points[n - 1], points[0], points[1]), 0);
        return result;
    }

    bool in_angle(Vector x, int i, int j) {
        assert(i <= j);
        return (!right_turn(points[0], points[i], x)) && (!left_turn(points[0], points[j], x));
    }

    bool have(Vector x) {
        int n = (int)points.size();
        if (!in_angle(x, 1, n - 1)) {
            return false;
        }
        int l = 1, r = n - 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (in_angle(x, 1, m)) {
                r = m;
            } else {
                l = m;
            }
        }
        assert(in_angle(x, 1, r));
        l = r - 1;
        return !double_less(sign_of_turn(points[l], points[r], x), 0);
    }

    friend ostream &operator<<(ostream &out, const Convex_Polygon &p) {
        for (Vector v : p.points) {
            out << v << '\n';
        }
        return out;
    }

    friend istream &operator>>(istream &in, Convex_Polygon &p) {
        int n;
        in >> n;
        p.points.resize(n);
        for (int i = 0; i < n; ++i) {
            in >> p.points[i];
        }
        assert(p.check_ccw());
        return in;
    }
};

Convex_Polygon convex_hull(Polygon p) {
    sort(all(p.points), [&](Vector a, Vector b) {
        return tie(a.x, a.y) < tie(b.x, b.y);
    });
    p.points.erase(unique(all(p.points)), p.points.end());
    int n = (int)p.points.size();
    Convex_Polygon hull;
    if (n < 3) {
        hull.points = p.points;
        return hull;
    }
    vector<Vector> up, down;
    for (int i = 0; i < n; ++i) {
        if (i == 0 || i == n - 1 || right_turn(p[0], p[i], p[n - 1])) {
            while (up.size() >= 2 && !right_turn(up[up.size() - 2], up.back(), p[i])) {
                up.pop_back();
            }
            up.push_back(p[i]);
        }
        if (i == 0 || i == n - 1 || left_turn(p[0], p[i], p[n - 1])) {
            while (down.size() >= 2 && !left_turn(down[down.size() - 2], down.back(), p[i])) {
                down.pop_back();
            }
            down.push_back(p[i]);
        }
    }
    hull.points = down;
    for (int i = (int)up.size() - 2; i >= 1; --i) {
        hull.points.push_back(up[i]);
    }
    return hull;
}


int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);

    Polygon p;
    cin >> p;
    cout << p << endl;

    Vector q;
    while (cin >> q) {
        cout << q << ": " << p.have(q) << endl;
    }

    return 0;
}