SHARE
TWEET

Untitled

a guest Jan 22nd, 2020 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef long double ld;
  6.  
  7. ld const eps = 1e-10;
  8. ll const LLINF = 1e18;
  9. int const INF = 1e9;
  10.  
  11. struct point {
  12.     ld x, y;
  13.     point() {}
  14.     point(ld xx, ld yy) : x(xx), y(yy) {}
  15.     point operator + (point const& a) const {
  16.         return point(x + a.x, y + a.y);
  17.     }
  18.     point operator - (point const&  a) const {
  19.         return point(x - a.x, y - a.y);
  20.     }
  21.     point operator * (ld k) const {
  22.         return point(x * k, y * k);
  23.     }
  24.     point operator / (ld k) const {
  25.         return point(x / k, y / k);
  26.     }
  27.     ld operator ^ (point const& a) const {
  28.         return (x * a.x + y * a.y);
  29.     }
  30.     ld operator % (point const&  a) const {
  31.         return (x * a.y - y * a.x);
  32.     }
  33.     bool operator != (point const& a) const {
  34.         return (x != a.x) || (y != a.y);
  35.     }
  36.     bool operator == (point const& a) const {
  37.         return (x == a.x) &&  (y == a.y);
  38.     }
  39.     bool operator < (point const& a) const {
  40.         if (x != a.x) return x < a.x;
  41.         return y < a.y;
  42.     }
  43. };
  44.  
  45. istream& operator >> (istream& in, point & a) {
  46.     return (in >> a.x >> a.y);
  47. }
  48.  
  49. ostream& operator << (ostream& out, point const&  a) {
  50.     return (out << a.x << ' ' << a.y);
  51. }
  52.  
  53. struct plane {
  54.     ll a, b, c;
  55.     plane(){}
  56.     plane(ll const& a, ll const&  b, ll const&  c) : a(a), b(b), c(c) {}
  57.     bool operator == (plane const&  o) const {
  58.         return a == o.a &&  b == o.b &&  c == o.c;
  59.     }
  60.     friend istream& operator >>(istream& in, plane & x) {
  61.         return (in >> x.a >> x.b >> x.c);
  62.     }
  63.     friend ostream& operator << (ostream& out, plane const& x) {
  64.         return (out << x.a << ' ' << x.b << ' ' << x.c);
  65.     }
  66. };
  67.  
  68. inline ll det(ll const&  a, ll const&  b, ll const&  c, ll const&  d) {
  69.     return a * d - b * c;
  70. }
  71.  
  72. bool intersect(plane m, plane n, point & res) {
  73.     ll zn = det(m.a, m.b, n.a, n.b);
  74.     if (abs(zn) <= 0)
  75.         return false;
  76.     res.x = (ld)-det(m.c, m.b, n.c, n.b) / zn;
  77.     res.y = (ld)-det(m.a, m.c, n.a, n.c) / zn;
  78.     return true;
  79. }
  80.  
  81. inline bool ok(plane const& p, point const& x) {
  82.     return x.x * p.a + x.y * p.b + p.c > -eps;
  83. }
  84.  
  85.  
  86. inline bool intersect(plane const& m, vector <plane> const& poly, int j) {
  87.     int n = poly.size();
  88.     point p1, p2;
  89.     assert(intersect(poly[j], poly[(j + n - 1) % n], p1));
  90.     assert(intersect(poly[j], poly[(j + 1) % n], p2));
  91.     bool s1 = ok(m, p1), s2 = ok(m, p2);
  92.     return s1 ^ s2;
  93. }
  94.  
  95. bool equivalent (plane m, plane n) {
  96.     return abs (det (m.a, m.b, n.a, n.b)) <= 0
  97.            && abs (det (m.a, m.c, n.a, n.c)) <= 0
  98.            && abs (det (m.b, m.c, n.b, n.c)) <= 0;
  99. }
  100.  
  101. inline int sign(ll x) {
  102.     if (x > 0) return 1;
  103.     if (x < 0) return -1;
  104.     return 0;
  105. }
  106.  
  107. void half_plane_intersection(vector <plane> const&  a) {
  108.     vector <plane> borders = {
  109.             {0, 1, INF},
  110.             {-1, 0, INF},
  111.             {0, -1, INF},
  112.             {1, 0, INF}
  113.     }, poly = borders;
  114.     point res;
  115.     for (plane const&  p : a) {
  116.         vector <int> ip;
  117.         for (int j = 0; j < poly.size(); j++) {
  118.             if (equivalent(p, poly[j])) {
  119.                 if (sign(p.a) != sign(poly[j].a) || sign(p.b) != sign(poly[j].b)) {
  120.                     cout << 0;
  121.                     return;
  122.                 }
  123.             } else if (intersect(p, poly, j)) {
  124.                 ip.push_back(j);
  125.             }
  126.         }
  127.         if (ip.empty()) {
  128.             intersect(poly[0], poly[1], res);
  129.             if (!ok(p, res)) {
  130.                 cout << 0;
  131.                 return;
  132.             } else {
  133.                 continue;
  134.             }
  135.         }
  136.         assert(ip.size() == 2);
  137.         assert(intersect(poly[ip[0]], poly[ip[0] + 1], res));
  138.         vector <plane> tmp;
  139.         if (!ok(p, res)) {
  140.             for (int j = 0; j < poly.size(); j++) if (j <= ip[0] || j >= ip[1]) {
  141.                 tmp.push_back(poly[j]);
  142.                 if (j == ip[0]) {
  143.                     tmp.push_back(p);
  144.                 }
  145.             }
  146.         } else {
  147.             tmp.push_back(p);
  148.             for (int j = ip[0]; j <= ip[1]; j++) tmp.push_back(poly[j]);
  149.         }
  150.         swap(poly, tmp);
  151.     }
  152.     for (plane& p : poly) {
  153.         for (plane& border : borders) {
  154.             if (p == border) {
  155.                 cout << -1;
  156.                 return;
  157.             }
  158.         }
  159.     }
  160.     int n = poly.size();
  161.     vector <point> pts;
  162.     for (int i = 0; i < n; i++) {
  163.         int j = (i + 1) % n;
  164.         assert(intersect(poly[i], poly[j], res));
  165.         pts.push_back(res);
  166.     }
  167.     ld ans = 0;
  168.     for (int i = 0; i < n; i++) {
  169.         int j = (i + 1) % n;
  170.         ans += pts[i] % pts[j];
  171.     }
  172.     cout << fixed << setprecision(20);
  173.     cout << abs(ans) / 2;
  174. }
  175.  
  176. int main() {
  177. #ifdef LOCAL
  178.     freopen("input.txt", "r", stdin);
  179. #endif
  180.     ios::sync_with_stdio(false);
  181.     cin.tie(nullptr);
  182.     int n;
  183.     cin >> n;
  184.     vector <plane> a(n);
  185.     for (int i = 0; i < n; i++) {
  186.         cin >> a[i];
  187.     }
  188.     half_plane_intersection(a);
  189.     return 0;
  190. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top