Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- ld const eps = 1e-10;
- ll const LLINF = 1e18;
- int const INF = 1e9;
- struct point {
- ld x, y;
- point() {}
- point(ld xx, ld yy) : x(xx), y(yy) {}
- point operator + (point const& a) const {
- return point(x + a.x, y + a.y);
- }
- point operator - (point const& a) const {
- return point(x - a.x, y - a.y);
- }
- point operator * (ld k) const {
- return point(x * k, y * k);
- }
- point operator / (ld k) const {
- return point(x / k, y / k);
- }
- ld operator ^ (point const& a) const {
- return (x * a.x + y * a.y);
- }
- ld operator % (point const& a) const {
- return (x * a.y - y * a.x);
- }
- bool operator != (point const& a) const {
- return (x != a.x) || (y != a.y);
- }
- bool operator == (point const& a) const {
- return (x == a.x) && (y == a.y);
- }
- bool operator < (point const& a) const {
- if (x != a.x) return x < a.x;
- return y < a.y;
- }
- };
- istream& operator >> (istream& in, point & a) {
- return (in >> a.x >> a.y);
- }
- ostream& operator << (ostream& out, point const& a) {
- return (out << a.x << ' ' << a.y);
- }
- struct plane {
- ll a, b, c;
- plane(){}
- plane(ll const& a, ll const& b, ll const& c) : a(a), b(b), c(c) {}
- bool operator == (plane const& o) const {
- return a == o.a && b == o.b && c == o.c;
- }
- friend istream& operator >>(istream& in, plane & x) {
- return (in >> x.a >> x.b >> x.c);
- }
- friend ostream& operator << (ostream& out, plane const& x) {
- return (out << x.a << ' ' << x.b << ' ' << x.c);
- }
- };
- inline ll det(ll const& a, ll const& b, ll const& c, ll const& d) {
- return a * d - b * c;
- }
- bool intersect(plane m, plane n, point & res) {
- ll zn = det(m.a, m.b, n.a, n.b);
- if (abs(zn) <= 0)
- return false;
- res.x = (ld)-det(m.c, m.b, n.c, n.b) / zn;
- res.y = (ld)-det(m.a, m.c, n.a, n.c) / zn;
- return true;
- }
- inline bool ok(plane const& p, point const& x) {
- return x.x * p.a + x.y * p.b + p.c > -eps;
- }
- inline bool intersect(plane const& m, vector <plane> const& poly, int j) {
- int n = poly.size();
- point p1, p2;
- assert(intersect(poly[j], poly[(j + n - 1) % n], p1));
- assert(intersect(poly[j], poly[(j + 1) % n], p2));
- bool s1 = ok(m, p1), s2 = ok(m, p2);
- return s1 ^ s2;
- }
- bool equivalent (plane m, plane n) {
- return abs (det (m.a, m.b, n.a, n.b)) <= 0
- && abs (det (m.a, m.c, n.a, n.c)) <= 0
- && abs (det (m.b, m.c, n.b, n.c)) <= 0;
- }
- inline int sign(ll x) {
- if (x > 0) return 1;
- if (x < 0) return -1;
- return 0;
- }
- void half_plane_intersection(vector <plane> const& a) {
- vector <plane> borders = {
- {0, 1, INF},
- {-1, 0, INF},
- {0, -1, INF},
- {1, 0, INF}
- }, poly = borders;
- point res;
- for (plane const& p : a) {
- vector <int> ip;
- for (int j = 0; j < poly.size(); j++) {
- if (equivalent(p, poly[j])) {
- if (sign(p.a) != sign(poly[j].a) || sign(p.b) != sign(poly[j].b)) {
- cout << 0;
- return;
- }
- } else if (intersect(p, poly, j)) {
- ip.push_back(j);
- }
- }
- if (ip.empty()) {
- intersect(poly[0], poly[1], res);
- if (!ok(p, res)) {
- cout << 0;
- return;
- } else {
- continue;
- }
- }
- assert(ip.size() == 2);
- assert(intersect(poly[ip[0]], poly[ip[0] + 1], res));
- vector <plane> tmp;
- if (!ok(p, res)) {
- for (int j = 0; j < poly.size(); j++) if (j <= ip[0] || j >= ip[1]) {
- tmp.push_back(poly[j]);
- if (j == ip[0]) {
- tmp.push_back(p);
- }
- }
- } else {
- tmp.push_back(p);
- for (int j = ip[0]; j <= ip[1]; j++) tmp.push_back(poly[j]);
- }
- swap(poly, tmp);
- }
- for (plane& p : poly) {
- for (plane& border : borders) {
- if (p == border) {
- cout << -1;
- return;
- }
- }
- }
- int n = poly.size();
- vector <point> pts;
- for (int i = 0; i < n; i++) {
- int j = (i + 1) % n;
- assert(intersect(poly[i], poly[j], res));
- pts.push_back(res);
- }
- ld ans = 0;
- for (int i = 0; i < n; i++) {
- int j = (i + 1) % n;
- ans += pts[i] % pts[j];
- }
- cout << fixed << setprecision(20);
- cout << abs(ans) / 2;
- }
- int main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- #endif
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- int n;
- cin >> n;
- vector <plane> a(n);
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- }
- half_plane_intersection(a);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement