//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "计算几何大板子": {
        "prefix": "acm-8.3Geometry",
        "body": [
            "namespace Geometry {",
            "using T = ll;",
            "constexpr T eps = 0;",
            "",
            "bool eq(const T &x, const T &y) { return abs(x - y) <= eps; }",
            "inline constexpr int type(T x, T y) {",
            "    if(x == 0 and y == 0) return 0;",
            "    if(y < 0 or (y == 0 and x > 0)) return -1;",
            "    return 1;",
            "}",
            "struct Point {",
            "    T x, y;",
            "    constexpr Point(T _x = 0, T _y = 0) : x(_x), y(_y) {}",
            "    constexpr Point operator+() const noexcept { return *this; }",
            "    constexpr Point operator-() const noexcept { return Point(-x, -y); }",
            "    constexpr Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }",
            "    constexpr Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }",
            "    constexpr Point &operator+=(const Point &p) { return x += p.x, y += p.y, *this; }",
            "    constexpr Point &operator-=(const Point &p) { return x -= p.x, y -= p.y, *this; }",
            "    constexpr T operator*(const Point &p) const { return x * p.x + y * p.y; }",
            "    constexpr Point &operator*=(const T &k) { return x *= k, y *= k, *this; }",
            "    constexpr Point operator*(const T &k) { return Point(x * k, y * k); }",
            "    constexpr bool operator==(const Point &r) const noexcept { return r.x == x and r.y == y; }",
            "    constexpr T cross(const Point &r) const { return x * r.y - y * r.x; }",
            "",
            "    constexpr bool operator<(const Point &r) const { return pair(x, y) < pair(r.x, r.y); }",
            "",
            "    // 1 : left, 0 : same, -1 : right",
            "    constexpr int toleft(const Point &r) const {",
            "        auto t = cross(r);",
            "        return t > eps ? 1 : t < -eps ? -1 : 0;",
            "    }",
            "",
            "    constexpr bool arg_cmp(const Point &r) const {",
            "        int L = type(x, y), R = type(r.x, r.y);",
            "        if(L != R) return L < R;",
            "",
            "        T X = x * r.y, Y = r.x * y;",
            "        if(X != Y) return X > Y;",
            "        return x < r.x;",
            "    }",
            "};",
            "bool arg_cmp(const Point &l, const Point &r) { return l.arg_cmp(r); }",
            "ostream &operator<<(ostream &os, const Point &p) { return os << p.x << \" \" << p.y; }",
            "istream &operator>>(istream &is, Point &p) {",
            "    is >> p.x >> p.y;",
            "    return is;",
            "}",
            "",
            "struct Line {",
            "    Point a, b;",
            "    Line() = default;",
            "    Line(Point a, Point b) : a(a), b(b) {}",
            "    // ax + by = c",
            "    Line(T A, T B, T C) {",
            "        if(A == 0) {",
            "            a = Point(0, C / B), b = Point(1, C / B);",
            "        } else if(B == 0) {",
            "            a = Point(C / A, 0), b = Point(C / A, 1);",
            "        } else {",
            "            a = Point(0, C / B), b = Point(C / A, 0);",
            "        }",
            "    }",
            "    // 1 : left, 0 : same, -1 : right",
            "    constexpr int toleft(const Point &r) const {",
            "        auto t = (b - a).cross(r - a);",
            "        return t > eps ? 1 : t < -eps ? -1 : 0;",
            "    }",
            "",
            "    friend std::ostream &operator<<(std::ostream &os, Line &ls) {",
            "        return os << \"{\"",
            "                  << \"(\" << ls.a.x << \", \" << ls.a.y << \"), (\" << ls.b.x << \", \" << ls.b.y << \")}\";",
            "    }",
            "};",
            "istream &operator>>(istream &is, Line &p) { return is >> p.a >> p.b; }",
            "",
            "struct Segment : Line {",
            "    Segment() = default;",
            "    Segment(Point a, Point b) : Line(a, b) {}",
            "};",
            "",
            "ostream &operator<<(ostream &os, Segment &p) { return os << p.a << \" to \" << p.b; }",
            "istream &operator>>(istream &is, Segment &p) {",
            "    is >> p.a >> p.b;",
            "    return is;",
            "}",
            "",
            "struct Circle {",
            "    Point p;",
            "    T r;",
            "    Circle() = default;",
            "    Circle(Point p, T r) : p(p), r(r) {}",
            "};",
            "",
            "using pt = Point;",
            "using Points = vector<pt>;",
            "using Polygon = Points;",
            "T cross(const pt &x, const pt &y) { return x.x * y.y - x.y * y.x; }",
            "T dot(const pt &x, const pt &y) { return x.x * y.x + x.y * y.y; }",
            "",
            "T abs2(const pt &x) { return dot(x, x); }",
            "// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C",
            "// 点の回転方向",
            "int ccw(const Point &a, Point b, Point c) {",
            "    b = b - a, c = c - a;",
            "    if(cross(b, c) > 0) return +1;   // \"COUNTER_CLOCKWISE\"",
            "    if(cross(b, c) < 0) return -1;   // \"CLOCKWISE\"",
            "    if(dot(b, c) < 0) return +2;     // \"ONLINE_BACK\"",
            "    if(abs2(b) < abs2(c)) return -2; // \"ONLINE_FRONT\"",
            "    return 0;                        // \"ON_SEGMENT\"",
            "}",
            "",
            "// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A",
            "// 平行判定",
            "bool parallel(const Line &a, const Line &b) { return (cross(a.b - a.a, b.b - b.a) == 0); }",
            "",
            "// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A",
            "// 垂直判定",
            "bool orthogonal(const Line &a, const Line &b) { return (dot(a.a - a.b, b.a - b.b) == 0); }",
            "",
            "bool intersect(const Line &l, const Point &p) { return abs(ccw(l.a, l.b, p)) != 1; }",
            "",
            "bool intersect(const Line &l, const Line &m) { return !parallel(l, m); }",
            "",
            "bool intersect(const Segment &s, const Point &p) { return ccw(s.a, s.b, p) == 0; }",
            "",
            "bool intersect(const Line &l, const Segment &s) { return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) <= 0; }",
            "",
            "// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B",
            "bool intersect(const Segment &s, const Segment &t) { return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0; }",
            "",
            "bool intersect(const Polygon &ps, const Polygon &qs) {",
            "    int pl = si(ps), ql = si(qs), i = 0, j = 0;",
            "    while((i < pl or j < ql) and (i < 2 * pl) and (j < 2 * ql)) {",
            "        auto ps0 = ps[(i + pl - 1) % pl], ps1 = ps[i % pl];",
            "        auto qs0 = qs[(j + ql - 1) % ql], qs1 = qs[j % ql];",
            "        if(intersect(Segment(ps0, ps1), Segment(qs0, qs1))) return true;",
            "        Point a = ps1 - ps0;",
            "        Point b = qs1 - qs0;",
            "        T v = cross(a, b);",
            "        T va = cross(qs1 - qs0, ps1 - qs0);",
            "        T vb = cross(ps1 - ps0, qs1 - ps0);",
            "",
            "        if(!v and va < 0 and vb < 0) return false;",
            "        if(!v and !va and !vb) {",
            "            i += 1;",
            "        } else if(v >= 0) {",
            "            if(vb > 0)",
            "                i += 1;",
            "            else",
            "                j += 1;",
            "        } else {",
            "            if(va > 0)",
            "                j += 1;",
            "            else",
            "                i += 1;",
            "        }",
            "    }",
            "    return false;",
            "}",
            "",
            "T norm(const Point &p) { return p.x * p.x + p.y * p.y; }",
            "Point projection(const Segment &l, const Point &p) {",
            "    T t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);",
            "    return l.a + (l.a - l.b) * t;",
            "}",
            "",
            "Point crosspoint(const Line &l, const Line &m) {",
            "    T A = cross(l.b - l.a, m.b - m.a);",
            "    T B = cross(l.b - l.a, l.b - m.a);",
            "    if(A == 0 and B == 0) return m.a;",
            "    return m.a + (m.b - m.a) * (B / A);",
            "}",
            "",
            "// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C",
            "Point crosspoint(const Segment &l, const Segment &m) { return crosspoint(Line(l), Line(m)); }",
            "",
            "// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_B",
            "// 凸性判定",
            "bool is_convex(const Points &p) {",
            "    int n = (int)p.size();",
            "    for(int i = 0; i < n; i++) {",
            "        if(ccw(p[(i + n - 1) % n], p[i], p[(i + 1) % n]) == -1) return false;",
            "    }",
            "    return true;",
            "}",
            "",
            "Points convex_hull(Points p) {",
            "    int n = p.size(), k = 0;",
            "    if(n <= 2) return p;",
            "    sort(begin(p), end(p), [](pt x, pt y) { return (x.x != y.x ? x.x < y.x : x.y < y.y); });",
            "    Points ch(2 * n);",
            "    for(int i = 0; i < n; ch[k++] = p[i++]) {",
            "        while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= 0) --k;",
            "    }",
            "    for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {",
            "        while(k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= 0) --k;",
            "    }",
            "    ch.resize(k - 1);",
            "    return ch;",
            "}",
            "",
            "// 面積の 2 倍",
            "T area2(const Points &p) {",
            "    T res = 0;",
            "    rep(i, si(p)) { res += cross(p[i], p[i == si(p) - 1 ? 0 : i + 1]); }",
            "    return res;",
            "}",
            "",
            "enum { _OUT, _ON, _IN };",
            "",
            "int contains(const Polygon &Q, const Point &p) {",
            "    bool in = false;",
            "    for(int i = 0; i < Q.size(); i++) {",
            "        Point a = Q[i] - p, b = Q[(i + 1) % Q.size()] - p;",
            "        if(a.y > b.y) swap(a, b);",
            "        if(a.y <= 0 && 0 < b.y && cross(a, b) < 0) in = !in;",
            "        if(cross(a, b) == 0 && dot(a, b) <= 0) return _ON;",
            "    }",
            "    return in ? _IN : _OUT;",
            "}",
            "",
            "Polygon Minkowski_sum(const Polygon &P, const Polygon &Q) {",
            "    vector<Segment> e1(P.size()), e2(Q.size()), ed(P.size() + Q.size());",
            "    const auto cmp = [](const Segment &u, const Segment &v) { return (u.b - u.a).arg_cmp(v.b - v.a); };",
            "    rep(i, P.size()) e1[i] = {P[i], P[(i + 1) % P.size()]};",
            "    rep(i, Q.size()) e2[i] = {Q[i], Q[(i + 1) % Q.size()]};",
            "    rotate(begin(e1), min_element(all(e1), cmp), end(e1));",
            "    rotate(begin(e2), min_element(all(e2), cmp), end(e2));",
            "    merge(all(e1), all(e2), begin(ed), cmp);",
            "    const auto check = [](const Points &res, const Point &u) {",
            "        const auto back1 = res.back(), back2 = *prev(end(res), 2);",
            "        return eq(cross(back1 - back2, u - back2), eps) and dot(back1 - back2, u - back1) >= -eps;",
            "    };",
            "    auto u = e1[0].a + e2[0].a;",
            "    Points res{u};",
            "    res.reserve(P.size() + Q.size());",
            "    for(const auto &v : ed) {",
            "        u = u + v.b - v.a;",
            "        while(si(res) >= 2 and check(res, u)) res.pop_back();",
            "        res.eb(u);",
            "    }",
            "    if(res.size() and check(res, res[0])) res.pop_back();",
            "    return res;",
            "}",
            "",
            "// -1 : on, 0 : out, 1 : in",
            "// O(log(n))",
            "int is_in(const Polygon &p, const Point &a) {",
            "    if(p.size() == 1) return a == p[0] ? -1 : 0;",
            "    if(p.size() == 2) return intersect(Segment(p[0], p[1]), a);",
            "    if(a == p[0]) return -1;",
            "    if((p[1] - p[0]).toleft(a - p[0]) == -1 || (p.back() - p[0]).toleft(a - p[0]) == 1) return 0;",
            "    const auto cmp = [&](const Point &u, const Point &v) { return (u - p[0]).toleft(v - p[0]) == 1; };",
            "    const size_t i = lower_bound(p.begin() + 1, p.end(), a, cmp) - p.begin();",
            "    if(i == 1) return intersect(Segment(p[0], p[i]), a) ? -1 : 0;",
            "    if(i == p.size() - 1 && intersect(Segment(p[0], p[i]), a)) return -1;",
            "    if(intersect(Segment(p[i - 1], p[i]), a)) return -1;",
            "    return (p[i] - p[i - 1]).toleft(a - p[i - 1]) > 0;",
            "}",
            "",
            "Points halfplane_intersection(vector<Line> L, const T inf = 1e9) {",
            "    Point box[4] = {Point(inf, inf), Point(-inf, inf), Point(-inf, -inf), Point(inf, -inf)};",
            "    rep(i, 4) { L.emplace_back(box[i], box[(i + 1) % 4]); }",
            "    sort(all(L), [](const Line &l, const Line &r) { return (l.b - l.a).arg_cmp(r.b - r.a); });",
            "    deque<Line> dq;",
            "    int len = 0;",
            "    auto check = [](const Line &a, const Line &b, const Line &c) { return a.toleft(crosspoint(b, c)) == -1; };",
            "    rep(i, L.size()) {",
            "        while(dq.size() > 1 and check(L[i], *(end(dq) - 2), *(end(dq) - 1))) dq.pop_back();",
            "        while(dq.size() > 1 and check(L[i], dq[0], dq[1])) dq.pop_front();",
            "        // dump(L[i], si(dq));",
            "",
            "        if(dq.size() and eq(cross(L[i].b - L[i].a, dq.back().b - dq.back().a), 0)) {",
            "            if(dot(L[i].b - L[i].a, dq.back().b - dq.back().a) < eps) return {};",
            "            if(L[i].toleft(dq.back().a) == -1)",
            "                dq.pop_back();",
            "            else",
            "                continue;",
            "        }",
            "        dq.emplace_back(L[i]);",
            "    }",
            "",
            "    while(dq.size() > 2 and check(dq[0], *(end(dq) - 2), *(end(dq) - 1))) dq.pop_back();",
            "    while(dq.size() > 2 and check(dq.back(), dq[0], dq[1])) dq.pop_front();",
            "    if(si(dq) < 3) return {};",
            "    Polygon ret(dq.size());",
            "    rep(i, dq.size()) ret[i] = crosspoint(dq[i], dq[(i + 1) % dq.size()]);",
            "    return ret;",
            "}",
            "} // namespace Geometry",
            "",
            "using namespace Geometry;"
        ],
        "description": "插入 计算几何大板子"
    }
}