Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2020
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.04 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement