Advertisement
Guest User

Untitled

a guest
Mar 25th, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const long long inf = 1e18;
  6.  
  7. struct Point {
  8. int x, y;
  9. Point operator-(const Point& p) const { return {x - p.x, y - p.y}; }
  10. int64_t operator^(const Point& p) const { return x * 1ll * p.y - y * 1ll * p.x; }
  11. int64_t dist() const { return x * 1ll * x + y * 1ll * y; }
  12. bool operator<(const Point& p) const { return x != p.x ? x < p.x : y < p.y; }
  13. };
  14.  
  15. // all point on convex hull are included
  16. vector<Point> convex_hull(vector<Point> pt) {
  17. int n = pt.size();
  18. Point p0 = *std::min_element(pt.begin(), pt.end());
  19. std::sort(pt.begin(), pt.end(), [&p0](const Point& a, const Point& b) {
  20. int64_t cp = (a - p0) ^ (b - p0);
  21. return cp != 0 ? cp > 0 : (a - p0).dist() < (b - p0).dist();
  22. });
  23.  
  24. int i = n - 1;
  25. for (; i > 0 && ((pt[i] - p0) ^ (pt[i - 1] - p0)) == 0; i--);
  26. std::reverse(pt.begin() + i, pt.end());
  27.  
  28. vector<Point> ch;
  29. for (auto& p : pt) {
  30. while (ch.size() > 1) {
  31. auto& p1 = ch[(int) ch.size() - 1];
  32. auto& p2 = ch[(int) ch.size() - 2];
  33. int64_t cp = (p1 - p2) ^ (p - p1);
  34. if (cp >= 0) break;
  35. ch.pop_back();
  36. }
  37. ch.push_back(p);
  38. }
  39.  
  40. return ch;
  41. }
  42.  
  43. int p[500500];
  44. int d[500500];
  45.  
  46.  
  47. long long func(Point a, Point b) {
  48. return (a.x - b.x) * 1ll * (a.y - b.y);
  49. }
  50.  
  51. int main() {
  52. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  53.  
  54. int m , n;
  55. cin >> m >> n;
  56.  
  57. for (int i = 0; i < m; i++)
  58. cin >> p[i] >> d[i];
  59.  
  60. vector<Point> ps;
  61.  
  62. for (int i = 0; i < n; i++) {
  63. int q, e;
  64. cin >> q >> e;
  65. ps.push_back({e, q});
  66. }
  67.  
  68. ps = convex_hull(ps);
  69.  
  70. auto it = max_element(ps.begin(), ps.end(), [](Point a, Point b) {
  71. return (a.x < b.x || (a.x == b.x && a.y < b.y));
  72. });
  73.  
  74. rotate(ps.begin(), it, ps.end());
  75.  
  76.  
  77. if (ps.size() != 1)
  78. for (int i = 0; i + 1 < ps.size(); i++) {
  79. int j = i + 1 == ps.size() ? 0 : i + 1;
  80.  
  81. if (!(ps[j].x < ps[i].x && ps[j].y > ps[i].y)) {
  82. ps.resize(j); // delete with j
  83. break;
  84. }
  85. }
  86.  
  87. long long ans = 0;
  88.  
  89. for (int i = 0; i < m; i++) {
  90. int x = d[i];
  91. int y = p[i];
  92.  
  93. Point p {x, y};
  94.  
  95. auto it1 = lower_bound(ps.begin(), ps.end(), Point{x, 0}, [](Point a, Point b) {
  96. return a.x > b.x;
  97. });
  98.  
  99. if (it1 == ps.begin())
  100. continue;
  101. it1--;
  102.  
  103. auto it2 = lower_bound(ps.begin(), ps.end(), Point{0, y}, [](Point a, Point b) {
  104. return a.y < b.y;
  105. });
  106.  
  107. int l = it2 - ps.begin();
  108. int r = it1 - ps.begin();
  109.  
  110. if (l > r)
  111. continue;
  112.  
  113. l--;
  114.  
  115. while (l + 1 < r) {
  116. int m1 = (l + r) / 2;
  117.  
  118. int m2 = m1 + 1;
  119. assert(m1 >= 0);
  120. assert(m2 <= r);
  121.  
  122. if (func(ps[m1], p) <= func(ps[m2], p)) {
  123. l = m1;
  124. } else {
  125. r = m1;
  126. }
  127. }
  128.  
  129. //cout << ps[r].x << " " << ps[r].y << " " << p.x << " " << p.y << " " << func(ps[r], p) << endl;
  130.  
  131. //cout << func(ps[r], p) << endl;
  132. //assert(false);
  133. ans = max(ans, func(ps[r], p));
  134. }
  135.  
  136. cout << ans;
  137.  
  138. return 0;
  139. }
  140.  
  141. /*
  142. 2 2
  143. 1 3
  144. 2 1
  145. 3 5
  146. 7 2
  147.  
  148. 1 1
  149. 0 1
  150. 1000000000 1000000001
  151.  
  152. 2 1
  153. 1000000 1
  154. 0 1
  155. 1000000000 1000000001
  156.  
  157. 1 1
  158. 0 2
  159. 10 2
  160.  
  161. 1 2
  162. 0 1
  163.  
  164. 8 2
  165. 10 2
  166.  
  167. 3 3
  168. 4 3
  169. 2 5
  170. 5 0
  171.  
  172. 1 3
  173. 3 2
  174. 4 1
  175. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement