Advertisement
cincout

M tinkoff

Sep 7th, 2019
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ld = long double;
  6.  
  7. ld eps = 1e-9;
  8.  
  9. bool equal(ld a, ld b) {
  10. return fabs(a - b) < eps;
  11. }
  12.  
  13. struct pt {
  14. ld x, y;
  15. pt(ld _x = 0, ld _y = 0) {
  16. x = _x;
  17. y = _y;
  18. }
  19. };
  20.  
  21. pt operator - (pt a, pt b) { return {a.x - b.x, a.y - b.y}; }
  22. ld operator * (pt a, pt b) { return a.x * b.y - b.x * a.y; }
  23. ld operator ^ (pt a, pt b) { return a.x * b.x + a.y * b.y; }
  24.  
  25. bool operator == (pt a, pt b) { return equal(a.x, b.x) && equal(a.y, b.y); }
  26. bool operator < (pt a, pt b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; }
  27.  
  28. struct line {
  29. ld a, b, c;
  30. line(ld _a = 0, ld _b = 0, ld _c = 0) {
  31. a = _a, b = _b, c = _c;
  32. }
  33. };
  34.  
  35. bool inter(line m, line n, pt & res) {
  36. ld zn = (pt(m.a, m.b) * pt(n.a, n.b));
  37. if (equal(zn, 0)) return 0;
  38. res.x = -(pt(m.c, m.b) * pt(n.c, n.b)) / zn;
  39. res.y = -(pt(m.a, m.c) * pt(n.a, n.c)) / zn;
  40. return 1;
  41. }
  42.  
  43. line toline(pt a, pt b) {
  44. return line(a.y - b.y, b.x - a.x, a * b);
  45. }
  46.  
  47. bool cmp(pt a, pt b) {
  48. return a * b > 0;
  49. }
  50.  
  51. bool hull(pt a, pt b) {
  52. if (a.y != b.y)
  53. return a.y < b.y;
  54. return a.x < b.x;
  55. }
  56.  
  57. struct polygon {
  58. vector <pt> data;
  59. void kek() {
  60. sort(data.begin(), data.end());
  61. data.erase(unique(data.begin(), data.end()), data.end());
  62. pt f = *min_element(data.begin(), data.end(), hull);
  63. for (auto &i : data) i = i - f;
  64. vector <pt> newdata;
  65. pt beg(0.0, 0.0);
  66. for (auto &i : data) if (!(i == beg)) newdata.push_back(i);
  67. sort(newdata.begin(), newdata.end(), cmp);
  68. newdata.insert(newdata.begin(), beg);
  69. f = {-f.x, -f.y};
  70. for (auto &i : newdata) i = i - f;
  71. swap(data, newdata);
  72. }
  73. };
  74.  
  75. bool on_line(pt a, pt b, pt c) {
  76. return (equal((b - a) * (c - a), 0) && ((c - a) ^ (c - b)) + 4 * 1e-14 < 0);
  77. }
  78.  
  79. bool cut(polygon &a, line t, polygon &b, polygon &c) {
  80. bool flag[2] = {0, 0};
  81. for (auto &i : a.data) {
  82. ld value = (t.a * i.x + t.b * i.y + t.c);
  83. if (equal(value, 0.0)) {
  84. b.data.push_back(i);
  85. c.data.push_back(i);
  86. }
  87. else if (value + 4 * 1e-14 < 0) {
  88. b.data.push_back(i);
  89. flag[0] = 1;
  90. }
  91. else {
  92. c.data.push_back(i);
  93. flag[1] = 1;
  94. }
  95. }
  96. if (!(flag[0] & flag[1])) return 0;
  97. for (int i = 0; i < a.data.size(); ++i) {
  98. int nxt = (i + 1) % a.data.size();
  99. line k = toline(a.data[i], a.data[nxt]);
  100. pt cross;
  101. if (inter(k, t, cross)) {
  102. if (on_line(a.data[i], a.data[nxt], cross)) {
  103. b.data.push_back(cross);
  104. c.data.push_back(cross);
  105. }
  106. }
  107. }
  108. b.kek(); c.kek();
  109. return 1;
  110. }
  111.  
  112. void solve() {
  113. ld x, y;
  114. cin >> x >> y;
  115. vector <polygon> base;
  116. base.push_back({{{0, 0}, {0, y}, {x, y}, {x, 0}}});
  117. int n; cin >> n;
  118. while (n--) {
  119. ld a, b, c;
  120. cin >> a >> b >> c;
  121. vector <polygon> add;
  122. vector <char> mark(base.size(), 0);
  123. for (int i = 0; i < base.size(); ++i) {
  124. polygon rofl, fun;
  125. if (cut(base[i], line(a, b, c), rofl, fun)) {
  126. add.push_back(rofl);
  127. add.push_back(fun);
  128. mark[i] = 1;
  129. }
  130. }
  131. vector <polygon> newbase;
  132. for (int i = 0; i < base.size(); ++i) if (!mark[i]) newbase.push_back(base[i]);
  133. for (auto i : add) newbase.push_back(i);
  134. swap(base, newbase);
  135. }
  136. int res = 0;
  137. for (auto i : base) if (i.data.size() == 3) res++;
  138. cout << res << '\n';
  139. }
  140.  
  141. int main() {
  142. ios::sync_with_stdio(0);
  143. cin.tie(0);
  144. solve();
  145. return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement