• API
• FAQ
• Tools
• Archive
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.
Top