Advertisement
Guest User

Untitled

a guest
Dec 13th, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <utility>
  5. #include <cmath>
  6. #include <set>
  7. #include <cstdlib>
  8. #include <map>
  9. #include <cassert>
  10.  
  11. using namespace std;
  12. typedef long long ll;
  13. typedef pair<int, int> pii;
  14. const double eps = 1e-5;
  15. const ll inf = 2e9;
  16. enum {BORDER_CONTAINS, CONTAIN, NOT_CONTAIN, CONTAIN_TOUCH, NOT_CONTAIN_TOUCH, INTERSECT};
  17. enum {P_CONTAINS, P_BORDER, P_NOT_CONTAINS};
  18.  
  19. inline double det (double a, double b, double c, double d) {
  20. return a * d - b * c;
  21. }
  22.  
  23. struct point {
  24. double x, y;
  25.  
  26. point(double x, double y): x(x), y(y) {}
  27.  
  28. void dump() { cout << "point: " << x << " " << y << "\n"; }
  29.  
  30. point copy() { return {x, y}; }
  31.  
  32. bool operator==(const point &o) const {
  33. return fabs(x - o.x) < eps && fabs(y - o.y) < eps;
  34. }
  35.  
  36. bool operator<(const point &o) const {
  37. return (x < o.x) || (x == o.x && y < o.y);
  38. }
  39. };
  40.  
  41. struct segment {
  42. point a, b;
  43.  
  44. segment(point a, point b): a(a), b(b) {}
  45.  
  46. void dump() const { cout << "segment: (" << a.x << " " << a.y << ") (" << b.x << " " << b.y << ")\n"; }
  47.  
  48. bool is_zro() {
  49. return fabs(a.x - b.x) < eps && fabs(b.y - a.y) < eps;
  50. }
  51.  
  52. };
  53.  
  54. struct halfplane {
  55. int a, b, c;
  56.  
  57. halfplane(int a, int b, int c): a(a), b(b), c(c) {}
  58. halfplane(int k1, int k2, int b, bool f): a(-k1), b(k2), c(-b) {}
  59. void dump() const { cout << "halfplane: " << a << "x+" << b << "y+" << c << ">0\n"; }
  60.  
  61. int contains(const point &p) const {
  62. double prod = a * p.x + b * p.y + c;
  63. if (fabs(prod) < eps) return P_BORDER;
  64. if (prod > eps) return P_CONTAINS;
  65.  
  66. return P_NOT_CONTAINS;
  67. }
  68.  
  69. int intersection_type(const segment &s) const {
  70. int in_a = contains(s.a), in_b = contains(s.b);
  71.  
  72. if ((in_a == P_BORDER) && (in_b == P_BORDER)) return BORDER_CONTAINS;
  73.  
  74. if (((in_a == P_BORDER) && (in_b == P_CONTAINS)) || ((in_a == P_CONTAINS) && (in_b == P_BORDER))) return CONTAIN_TOUCH;
  75.  
  76. if (((in_a == P_BORDER) && (in_b == P_NOT_CONTAINS)) || ((in_a == P_NOT_CONTAINS) && (in_b == P_BORDER))) return NOT_CONTAIN_TOUCH;
  77.  
  78. if (in_a == P_CONTAINS && in_b == P_CONTAINS) return CONTAIN;
  79.  
  80. if (in_a == P_NOT_CONTAINS && in_b == P_NOT_CONTAINS) return NOT_CONTAIN;
  81.  
  82. return INTERSECT;
  83.  
  84. }
  85.  
  86. point intersection_point(const segment &s) const {
  87. double A1 = a, B1 = b, C1 = c;
  88. double A2 = s.a.y - s.b.y, B2 = s.b.x - s.a.x, C2 = -A2 * s.a.x - B2 * s.a.y;
  89. double zn = det(A1, B1, A2, B2);
  90.  
  91. double x = - det(C1, B1, C2, B2) * 1. / zn;
  92. double y = - det(A1, C1, A2, C2) * 1. / zn;
  93. return {x, y};
  94. }
  95. };
  96.  
  97. struct hull {
  98. vector<segment> segments;
  99.  
  100. hull(vector<segment> &segments): segments(segments) {}
  101.  
  102. void dump() const {
  103. cout << "polygon size = " << segments.size() << "\n";
  104. for (const segment &s: segments) s.dump();
  105. cout << endl;
  106. }
  107.  
  108. void intersect_by(const halfplane &hp) {
  109. vector<segment> updated_segments;
  110. bool contains_segment = false;
  111. for (segment &s: segments) {
  112. int type = hp.intersection_type(s);
  113. switch (type) {
  114. case BORDER_CONTAINS:
  115. updated_segments.push_back(s);
  116. contains_segment = true;
  117. break;
  118. case CONTAIN:
  119. updated_segments.push_back(s);
  120. break;
  121. case NOT_CONTAIN:
  122. break;
  123. case CONTAIN_TOUCH:
  124. updated_segments.push_back(s);
  125. break;
  126. case NOT_CONTAIN_TOUCH:
  127. break;
  128. case INTERSECT:
  129. point intersection_point = hp.intersection_point(s);
  130. segment s1(s.a, intersection_point), s2(intersection_point, s.b);
  131. int s1t = hp.intersection_type(s1);
  132. if (s1t == CONTAIN || s1t == CONTAIN_TOUCH) {
  133. updated_segments.push_back(s1);
  134. } else {
  135. updated_segments.push_back(s2);
  136. }
  137. break;
  138. }
  139. }
  140.  
  141. if (contains_segment) {
  142. if (updated_segments.size() == 1) {
  143. cout << "0\n";
  144. exit(0);
  145. } else {
  146. return;
  147. }
  148. }
  149.  
  150. if (updated_segments.size() < 2) {
  151. cout << "0\n";
  152. exit(0);
  153. }
  154.  
  155. segments = updated_segments;
  156. if (segments.size() > 1) {
  157. vector<segment> res;
  158. for (int i = 0; i < segments.size() - 1; ++i) {
  159. if(!(segments[i].b == segments[i + 1].a)) {
  160. res.push_back(segments[i]);
  161. res.emplace_back(segments[i].b, segments[i + 1].a);
  162. } else {
  163. res.push_back(segments[i]);
  164. }
  165. }
  166.  
  167. if(!(segments[segments.size() - 1].b == segments[0].a)) {
  168. res.push_back(segments[segments.size() - 1]);
  169. res.emplace_back(segments[segments.size() - 1].b, segments[0].a);
  170. } else {
  171. res.push_back(segments[segments.size() - 1]);
  172. }
  173. segments = res;
  174. }
  175. }
  176.  
  177. // число отрезков лежащих на границе баундинг бокса
  178. bool has_init_segments() const {
  179. int lc = 0, rc = 0, tc = 0, bc = 0;
  180. for (const segment &s: segments) {
  181. lc += (fabs(s.a.x + inf) < eps && fabs(s.b.x + inf) < eps);
  182. rc += (fabs(s.a.x - inf) < eps && fabs(s.b.x - inf) < eps);
  183. tc += (fabs(s.a.y - inf) < eps && fabs(s.b.y - inf) < eps);
  184. bc += (fabs(s.a.y + inf) < eps && fabs(s.b.y + inf) < eps);
  185. }
  186.  
  187. return lc + tc + bc + rc > 0;
  188. }
  189.  
  190. double sq() const {
  191. if (has_init_segments()) return -1;
  192. double res = 0;
  193. for (const segment &s: segments) {
  194. res += (s.a.x - s.b.x) * (s.a.y + s.b.y);
  195. }
  196.  
  197. return fabs(res) / 2;
  198. }
  199. };
  200.  
  201. int main() {
  202. ios_base::sync_with_stdio(false);
  203. cout.precision(10);
  204. cout << fixed;
  205. int n;
  206. cin >> n;
  207. vector<halfplane> halfplanes;
  208. for (int i = 0; i < n; ++i) {
  209. int a, b, c;
  210. cin >> a >> b >> c;
  211. halfplanes.emplace_back(a, b, c);
  212. }
  213.  
  214. point top_left = {-inf, inf};
  215. point top_right = {inf, inf};
  216. point bottom_left = {-inf, -inf};
  217. point bottom_right = {inf, -inf};
  218. segment left(top_left, bottom_left);
  219. segment bottom(bottom_left, bottom_right);
  220. segment right(bottom_right, top_right);
  221. segment top(top_right, top_left);
  222.  
  223. vector<segment> bounding_box = {left, bottom, right, top};
  224.  
  225. hull h(bounding_box);
  226. for (halfplane &hp: halfplanes) {
  227. h.intersect_by(hp);
  228. }
  229.  
  230. cout << h.sq();
  231. return 0;
  232. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement