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; 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 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 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 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;