Advertisement
a53

Elmer

a53
Oct 5th, 2017
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.05 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long int lld;
  6. typedef pair<lld, lld> Point;
  7. const lld INF = (1LL << 60) - 1;
  8. const lld NMAX = 1e3;
  9. const lld MMAX = 1e3;
  10.  
  11. void read();
  12. void solve();
  13. void print();
  14.  
  15. int N, M, sol;
  16. vector<Point> ducks;
  17. vector<Point> walls;
  18. vector<Point> E;
  19.  
  20. struct eventCmp {
  21. bool operator()(const Point& e1, const Point &e2) const {
  22. if (e1.first == e2.first)
  23. return e1.second > e2.second;
  24. return e1.first < e2.first;
  25. }
  26. };
  27.  
  28. lld cp(Point& A, Point& B, Point& C) {
  29. return (A.first - C.first) * 1LL * (B.second - C.second) - (A.second - C.second) * 1LL * (B.first - C.first);
  30. }
  31.  
  32. lld find_min_pos(Point& duck, vector<Point>& S) {
  33. if (duck.second <= S[0].second)
  34. return INF;
  35. double x = (S[0].first * 1LL * duck.second - duck.first * 1LL * S[0].second) * 1.0 / (duck.second - S[0].second);
  36. return (fabs(x) - (lld)x <= 1e-6) ? x : x + 1.0;
  37. }
  38.  
  39. lld find_max_pos(Point& duck, vector<Point>& S) {
  40. if (duck.second <= S[0].second)
  41. return -INF;
  42. double x = (S[0].first * 1LL * duck.second - duck.first * 1LL * S[0].second) * 1.0 / (duck.second - S[0].second);
  43. return x;
  44. }
  45.  
  46. int main() {
  47. freopen("elmer.in", "r", stdin);
  48. freopen("elmer.out", "w", stdout);
  49.  
  50. read();
  51. solve();
  52. print();
  53.  
  54. return 0;
  55. }
  56.  
  57. void read() {
  58. scanf("%d", &N);
  59.  
  60. assert(1 <= N && N <= 1000);
  61.  
  62. for (int i = 1, x, y; i <= N; i++) {
  63. scanf("%d%d", &x, &y);
  64. assert(1 <= x && x <= 1000000000);
  65. assert(1 <= y && y <= 1000000000);
  66. ducks.push_back(make_pair(x, y));
  67. }
  68.  
  69. walls.push_back(make_pair(0, 0));
  70.  
  71. scanf("%d", &M);
  72.  
  73. assert(1 <= M && M <= 1000);
  74.  
  75. for (int i = 1, x, h; i <= M; i++) {
  76. scanf("%d%d", &x, &h);
  77. assert(1 <= x && x <= 1000000000);
  78. assert(1 <= h && h <= 1000000000);
  79. walls.push_back(make_pair(x, h));
  80. }
  81.  
  82. M += 2;
  83.  
  84. walls.push_back(make_pair(INF, 0));
  85. }
  86.  
  87. void solve() {
  88. lld L[NMAX + 5];
  89. lld R[NMAX + 5];
  90.  
  91. sort(ducks.begin(), ducks.end());
  92. sort(walls.begin(), walls.end());
  93.  
  94. for (int i = 0; i < N; i++) {
  95. Point duck = ducks[i];
  96.  
  97. int lb = (int)(lower_bound(walls.begin(), walls.end(), duck) - walls.begin());
  98. vector<Point> S;
  99.  
  100. for (int j = lb; j < M; j++) {
  101. Point wall = walls[j];
  102.  
  103. while (!S.empty() && cp(duck, S.back(), wall) >= 0)
  104. S.pop_back();
  105. S.push_back(wall);
  106.  
  107. L[j] = find_min_pos(duck, S);
  108. R[j] = INF - 1;
  109. }
  110.  
  111. S.clear();
  112.  
  113. for (int j = lb - 1; j >= 0; j--) {
  114. Point wall = walls[j];
  115.  
  116. while (!S.empty() && cp(duck, S.back(), wall) <= 0)
  117. S.pop_back();
  118. S.push_back(wall);
  119.  
  120. L[j] = -INF + 1;
  121. R[j] = find_max_pos(duck, S);
  122. }
  123.  
  124. for (int j = 0; j + 1 < M; j++) {
  125. lld l, r;
  126.  
  127. l = max(walls[j].first + 1LL, L[j]);
  128. r = min(walls[j + 1].first - 1LL, R[j + 1]);
  129.  
  130. if (l <= r) {
  131. E.push_back(make_pair(l, 1));
  132. E.push_back(make_pair(r, -1));
  133. }
  134. }
  135. }
  136.  
  137. sort(E.begin(), E.end(), eventCmp());
  138.  
  139. int hit = 0;
  140.  
  141. for (auto event = E.begin(); event != E.end(); event++) {
  142. hit += event->second;
  143. sol = max(sol, hit);
  144. }
  145. }
  146.  
  147. void print() {
  148. printf("%d\n", sol);
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement