Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <utility>
- #include <cmath>
- #include <set>
- #include <cstdlib>
- #include <map>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- const double eps = 1e-5;
- const ll inf = 2e9;
- enum {BORDER_CONTAINS, CONTAIN, NOT_CONTAIN, CONTAIN_TOUCH, NOT_CONTAIN_TOUCH, INTERSECT};
- enum {P_CONTAINS, P_BORDER, P_NOT_CONTAINS};
- inline double det (double a, double b, double c, double d) {
- return a * d - b * c;
- }
- struct point {
- double x, y;
- point(double x, double y): x(x), y(y) {}
- void dump() { cout << "point: " << x << " " << y << "\n"; }
- point copy() { return {x, y}; }
- bool operator==(const point &o) const {
- return fabs(x - o.x) < eps && fabs(y - o.y) < eps;
- }
- bool operator<(const point &o) const {
- return (x < o.x) || (x == o.x && y < o.y);
- }
- };
- struct segment {
- point a, b;
- segment(point a, point b): a(a), b(b) {}
- void dump() const { cout << "segment: (" << a.x << " " << a.y << ") (" << b.x << " " << b.y << ")\n"; }
- bool is_zro() {
- return fabs(a.x - b.x) < eps && fabs(b.y - a.y) < eps;
- }
- };
- struct halfplane {
- int a, b, c;
- halfplane(int a, int b, int c): a(a), b(b), c(c) {}
- halfplane(int k1, int k2, int b, bool f): a(-k1), b(k2), c(-b) {}
- void dump() const { cout << "halfplane: " << a << "x+" << b << "y+" << c << ">0\n"; }
- int contains(const point &p) const {
- double prod = a * p.x + b * p.y + c;
- if (fabs(prod) < eps) return P_BORDER;
- if (prod > eps) return P_CONTAINS;
- return P_NOT_CONTAINS;
- }
- int intersection_type(const segment &s) const {
- int in_a = contains(s.a), in_b = contains(s.b);
- if ((in_a == P_BORDER) && (in_b == P_BORDER)) return BORDER_CONTAINS;
- if (((in_a == P_BORDER) && (in_b == P_CONTAINS)) || ((in_a == P_CONTAINS) && (in_b == P_BORDER))) return CONTAIN_TOUCH;
- if (((in_a == P_BORDER) && (in_b == P_NOT_CONTAINS)) || ((in_a == P_NOT_CONTAINS) && (in_b == P_BORDER))) return NOT_CONTAIN_TOUCH;
- if (in_a == P_CONTAINS && in_b == P_CONTAINS) return CONTAIN;
- if (in_a == P_NOT_CONTAINS && in_b == P_NOT_CONTAINS) return NOT_CONTAIN;
- return INTERSECT;
- }
- point intersection_point(const segment &s) const {
- double A1 = a, B1 = b, C1 = c;
- double A2 = s.a.y - s.b.y, B2 = s.b.x - s.a.x, C2 = -A2 * s.a.x - B2 * s.a.y;
- double zn = det(A1, B1, A2, B2);
- double x = - det(C1, B1, C2, B2) * 1. / zn;
- double y = - det(A1, C1, A2, C2) * 1. / zn;
- return {x, y};
- }
- };
- struct hull {
- vector<segment> segments;
- hull(vector<segment> &segments): segments(segments) {}
- void dump() const {
- cout << "polygon size = " << segments.size() << "\n";
- for (const segment &s: segments) s.dump();
- cout << endl;
- }
- void intersect_by(const halfplane &hp) {
- vector<segment> updated_segments;
- bool contains_segment = false;
- for (segment &s: segments) {
- int type = hp.intersection_type(s);
- switch (type) {
- case BORDER_CONTAINS:
- updated_segments.push_back(s);
- contains_segment = true;
- break;
- case CONTAIN:
- updated_segments.push_back(s);
- break;
- case NOT_CONTAIN:
- break;
- case CONTAIN_TOUCH:
- updated_segments.push_back(s);
- break;
- case NOT_CONTAIN_TOUCH:
- break;
- case INTERSECT:
- point intersection_point = hp.intersection_point(s);
- segment s1(s.a, intersection_point), s2(intersection_point, s.b);
- int s1t = hp.intersection_type(s1);
- if (s1t == CONTAIN || s1t == CONTAIN_TOUCH) {
- updated_segments.push_back(s1);
- } else {
- updated_segments.push_back(s2);
- }
- break;
- }
- }
- if (contains_segment) {
- if (updated_segments.size() == 1) {
- cout << "0\n";
- exit(0);
- } else {
- return;
- }
- }
- if (updated_segments.size() < 2) {
- cout << "0\n";
- exit(0);
- }
- segments = updated_segments;
- if (segments.size() > 1) {
- vector<segment> res;
- for (int i = 0; i < segments.size() - 1; ++i) {
- if(!(segments[i].b == segments[i + 1].a)) {
- res.push_back(segments[i]);
- res.emplace_back(segments[i].b, segments[i + 1].a);
- } else {
- res.push_back(segments[i]);
- }
- }
- if(!(segments[segments.size() - 1].b == segments[0].a)) {
- res.push_back(segments[segments.size() - 1]);
- res.emplace_back(segments[segments.size() - 1].b, segments[0].a);
- } else {
- res.push_back(segments[segments.size() - 1]);
- }
- segments = res;
- }
- }
- // число отрезков лежащих на границе баундинг бокса
- bool has_init_segments() const {
- int lc = 0, rc = 0, tc = 0, bc = 0;
- for (const segment &s: segments) {
- lc += (fabs(s.a.x + inf) < eps && fabs(s.b.x + inf) < eps);
- rc += (fabs(s.a.x - inf) < eps && fabs(s.b.x - inf) < eps);
- tc += (fabs(s.a.y - inf) < eps && fabs(s.b.y - inf) < eps);
- bc += (fabs(s.a.y + inf) < eps && fabs(s.b.y + inf) < eps);
- }
- return lc + tc + bc + rc > 0;
- }
- double sq() const {
- if (has_init_segments()) return -1;
- double res = 0;
- for (const segment &s: segments) {
- res += (s.a.x - s.b.x) * (s.a.y + s.b.y);
- }
- return fabs(res) / 2;
- }
- };
- int main() {
- ios_base::sync_with_stdio(false);
- cout.precision(10);
- cout << fixed;
- int n;
- cin >> n;
- vector<halfplane> halfplanes;
- for (int i = 0; i < n; ++i) {
- int a, b, c;
- cin >> a >> b >> c;
- halfplanes.emplace_back(a, b, c);
- }
- point top_left = {-inf, inf};
- point top_right = {inf, inf};
- point bottom_left = {-inf, -inf};
- point bottom_right = {inf, -inf};
- segment left(top_left, bottom_left);
- segment bottom(bottom_left, bottom_right);
- segment right(bottom_right, top_right);
- segment top(top_right, top_left);
- vector<segment> bounding_box = {left, bottom, right, top};
- hull h(bounding_box);
- for (halfplane &hp: halfplanes) {
- h.intersect_by(hp);
- }
- cout << h.sq();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement