Fu_L's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Fu-L/cp-library

:heavy_check_mark: verify/aizu_online_judge/cgl/convex_cut.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/4/CGL_4_C"
#define ERROR 0.00001
#include "../../../src/template/template.hpp"
#include "../../../src/geometry/template.hpp"
#include "../../../src/geometry/point_2d.hpp"
#include "../../../src/geometry/polygon_2d.hpp"
int main(void) {
    int n;
    cin >> n;
    vector<Point> polygon(n);
    rep(i, 0, n) {
        cin >> polygon[i];
    }
    int q;
    cin >> q;
    while(q--) {
        Point p1, p2;
        cin >> p1 >> p2;
        Line l = Line(p1, p2);
        vector<Point> cut = convex_cut(polygon, l);
        cout << area(cut) << '\n';
    }
}
#line 1 "verify/aizu_online_judge/cgl/convex_cut.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/4/CGL_4_C"
#define ERROR 0.00001
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/geometry/template.hpp"
using Real = long double;
constexpr Real EPS = Real(1e-8), PI = 3.141592653589793238462643383279L;
int sign(const Real& r) {
    if(r <= -EPS) return -1;
    if(r >= +EPS) return +1;
    return 0;
}
bool eq(const Real& a, const Real& b) {
    return sign(a - b) == 0;
}
#line 4 "src/geometry/point_2d.hpp"
using Point = complex<Real>;
istream& operator>>(istream& is, Point& p) {
    Real a, b;
    is >> a >> b;
    p = Point(a, b);
    return is;
}
ostream& operator<<(ostream& os, const Point& p) {
    return os << p.real() << " " << p.imag();
}
Point operator*(const Point& p, const Real& d) {
    return Point(p.real() * d, p.imag() * d);
}
Point operator/(const Point& p, const Real& d) {
    return Point(p.real() / d, p.imag() / d);
}
Point rot(const Point& p, const Real& theta) {
    return p * Point(cos(theta), sin(theta));
}
Real dot(const Point& p1, const Point& p2) {
    return (conj(p1) * p2).real();
}
Real cross(const Point& p1, const Point& p2) {
    return (conj(p1) * p2).imag();
}
Real dist(const Point& p1, const Point& p2) {
    return abs(p1 - p2);
}
bool comp_x(const Point& p1, const Point& p2) {
    return eq(p1.real(), p2.real()) ? p1.imag() < p2.imag() : p1.real() < p2.real();
}
bool comp_y(const Point& p1, const Point& p2) {
    return eq(p1.imag(), p2.imag()) ? p1.real() < p2.real() : p1.imag() < p2.imag();
}
bool comp_arg(const Point& p1, const Point& p2) {
    return arg(p1) < arg(p2);
}
int ccw(const Point& a, Point b, Point c) {
    b -= a;
    c -= a;
    if(sign(cross(b, c)) == 1) return 1;
    if(sign(cross(b, c)) == -1) return -1;
    if(sign(dot(b, c)) == -1) return +2;
    if(norm(b) < norm(c)) return -2;
    return 0;
}
Real closest_pair(vector<Point> ps) {
    if((int)ps.size() <= 1) return Real(1e18);
    sort(ps.begin(), ps.end(), comp_x);
    vector<Point> memo(ps.size());
    auto func = [&](const auto& func, const int l, const int r) -> Real {
        if(r - l <= 1) return Real(1e18);
        const int m = (l + r) >> 1;
        const Real x = ps[m].real();
        Real res = min(func(func, l, m), func(func, m, r));
        inplace_merge(ps.begin() + l, ps.begin() + m, ps.begin() + r, comp_y);
        int cnt = 0;
        for(int i = l; i < r; ++i) {
            if(abs(ps[i].real() - x) >= res) continue;
            for(int j = 0; j < cnt; ++j) {
                const Point d = ps[i] - memo[cnt - j - 1];
                if(d.imag() >= res) break;
                res = min(res, abs(d));
            }
            memo[cnt++] = ps[i];
        }
        return res;
    };
    return func(func, 0, (int)ps.size());
}
#line 5 "src/geometry/line_and_segment_2d.hpp"
struct Line {
    Point a, b;
    Line() = default;
    Line(const Point& a, const Point& b)
        : a(a), b(b) {}
};
using Segment = Line;
bool is_parallel(const Line& a, const Line& b) {
    return eq(cross(a.b - a.a, b.b - b.a), 0.0);
}
bool is_orthogonal(const Line& a, const Line& b) {
    return eq(dot(a.b - a.a, b.b - b.a), 0.0);
}
Point projection(const Line& l, const Point& p) {
    Real t = dot(p - l.a, l.b - l.a) / norm(l.b - l.a);
    return l.a + (l.b - l.a) * t;
}
Point reflection(const Line& l, const Point& p) {
    return p + (projection(l, p) - p) * 2.0;
}
bool is_intersect_lp(const Line& l, const Point& p) {
    return abs(ccw(l.a, l.b, p)) != 1;
}
bool is_intersect_sp(const Segment& s, const Point& p) {
    return ccw(s.a, s.b, p) == 0;
}
bool is_intersect_ll(const Line& l1, const Line& l2) {
    if(!eq(cross(l1.b - l1.a, l2.b - l2.a), 0.0)) return true;
    return eq(cross(l1.b - l1.a, l2.b - l1.a), 0.0);
}
bool is_intersect_ls(const Line& l, const Segment& s) {
    return sign(cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a)) <= 0;
}
bool is_intersect_sl(const Segment& s, const Line& l) {
    return is_intersect_ls(l, s);
}
bool is_intersect_ss(const Segment& s1, const Segment& s2) {
    if(ccw(s1.a, s1.b, s2.a) * ccw(s1.a, s1.b, s2.b) > 0) return false;
    return ccw(s2.a, s2.b, s1.a) * ccw(s2.a, s2.b, s1.b) <= 0;
}
vector<Point> intersection_ll(const Line& l1, const Line& l2) {
    vector<Point> res;
    if(!is_intersect_ll(l1, l2)) return res;
    Real a = cross(l1.b - l1.a, l2.b - l2.a);
    Real b = cross(l1.b - l1.a, l1.b - l2.a);
    if(eq(a, 0.0) and eq(b, 0.0)) {
        res.emplace_back(l2.a);
    } else {
        res.emplace_back(l2.a + (l2.b - l2.a) * b / a);
    }
    return res;
}
vector<Point> intersection_ss(const Segment& s1, const Segment& s2) {
    return is_intersect_ss(s1, s2) ? intersection_ll(Line(s1), Line(s2)) : vector<Point>();
}
Real dist_lp(const Line& l, const Point& p) {
    return abs(p - projection(l, p));
}
Real dist_sp(const Segment& s, const Point& p) {
    const Point h = projection(s, p);
    if(is_intersect_sp(s, h)) return abs(h - p);
    return min(abs(s.a - p), abs(s.b - p));
}
Real dist_ll(const Line& l1, const Line& l2) {
    if(is_intersect_ll(l1, l2)) return 0.0;
    return dist_lp(l1, l2.a);
}
Real dist_ss(const Segment& s1, const Segment& s2) {
    if(is_intersect_ss(s1, s2)) return 0.0;
    return min({dist_sp(s1, s2.a), dist_sp(s1, s2.b), dist_sp(s2, s1.a), dist_sp(s2, s1.b)});
}
Real dist_ls(const Line& l, const Segment& s) {
    if(is_intersect_ls(l, s)) return 0.0;
    return min(dist_lp(l, s.a), dist_lp(l, s.b));
}
Real dist_sl(const Segment& s, const Line& l) {
    return dist_ls(l, s);
}
#line 6 "src/geometry/polygon_2d.hpp"
Real area(const vector<Point>& polygon) {
    Real res = 0.0;
    const int n = (int)polygon.size();
    for(int i = 0; i < n; ++i) {
        res += cross(polygon[i], polygon[(i + 1) % n]);
    }
    return abs(res * 0.5);
}
bool is_convex(const vector<Point>& polygon) {
    const int n = (int)polygon.size();
    for(int i = 0; i < n; ++i) {
        if(ccw(polygon[(i - 1 + n) % n], polygon[i], polygon[(i + 1) % n]) == -1) return false;
    }
    return true;
}
int in_polygon(const vector<Point>& polygon, const Point& p) {
    const int n = (int)polygon.size();
    int ret = 0;
    for(int i = 0; i < n; ++i) {
        Point a = polygon[i] - p, b = polygon[(i + 1) % n] - p;
        if(eq(cross(a, b), 0.0) and sign(dot(a, b)) <= 0) return 1;
        if(a.imag() > b.imag()) swap(a, b);
        if(sign(a.imag()) <= 0 and sign(b.imag()) == 1 and sign(cross(a, b)) == 1) ret ^= 2;
    }
    return ret;
}
vector<Point> convex_hull(vector<Point> ps) {
    sort(ps.begin(), ps.end(), comp_x);
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    const int n = (int)ps.size();
    if(n == 1) return ps;
    vector<Point> ch(2 * n);
    int k = 0;
    for(int i = 0; i < n; ch[k++] = ps[i++]) {
        while(k >= 2 and sign(cross(ch[k - 1] - ch[k - 2], ps[i] - ch[k - 1])) == -1) {
            --k;
        }
    }
    for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--]) {
        while(k >= t and sign(cross(ch[k - 1] - ch[k - 2], ps[i] - ch[k - 1])) == -1) {
            --k;
        }
    }
    ch.resize(k - 1);
    return ch;
}
Real convex_diameter(const vector<Point>& polygon) {
    const int n = (int)polygon.size();
    int is = 0, js = 0;
    for(int i = 1; i < n; ++i) {
        if(sign(polygon[i].imag() - polygon[is].imag()) == 1) is = i;
        if(sign(polygon[i].imag() - polygon[js].imag()) == -1) js = i;
    }
    Real maxdis = norm(polygon[is] - polygon[js]);
    int i = is, j = js;
    do {
        if(sign(cross(polygon[(i + 1) % n] - polygon[i], polygon[(j + 1) % n] - polygon[j])) >= 0) {
            j = (j + 1) % n;
        } else {
            i = (i + 1) % n;
        }
        if(norm(polygon[i] - polygon[j]) > maxdis) {
            maxdis = norm(polygon[i] - polygon[j]);
        }
    } while(i != is or j != js);
    return sqrt(maxdis);
}
vector<Point> convex_cut(const vector<Point>& polygon, const Line& l) {
    const int n = (int)polygon.size();
    vector<Point> res;
    for(int i = 0; i < n; ++i) {
        const Point cur = polygon[i], nex = polygon[(i + 1) % n];
        if(ccw(l.a, l.b, cur) != -1) res.emplace_back(cur);
        if(ccw(l.a, l.b, cur) * ccw(l.a, l.b, nex) < 0) {
            res.emplace_back(intersection_ll(Line(cur, nex), l)[0]);
        }
    }
    return res;
}
#line 7 "verify/aizu_online_judge/cgl/convex_cut.test.cpp"
int main(void) {
    int n;
    cin >> n;
    vector<Point> polygon(n);
    rep(i, 0, n) {
        cin >> polygon[i];
    }
    int q;
    cin >> q;
    while(q--) {
        Point p1, p2;
        cin >> p1 >> p2;
        Line l = Line(p1, p2);
        vector<Point> cut = convex_cut(polygon, l);
        cout << area(cut) << '\n';
    }
}
Back to top page