Advertisement
limimage

TASKL

Apr 21st, 2020
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.65 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int w, h, a, b, n, ans = 0, x_ans, y_ans;
  6. vector<pair<int, bool>> events;
  7. vector<tuple<int, int, int, int>> all;
  8.  
  9. void check(int u, int d, tuple<int, int, int, int> t) {
  10. auto [x1, y1, x2, y2] = t;
  11. if (y2 <= d || y1 >= u)
  12. return;
  13. events.emplace_back(x1, 1);
  14. events.emplace_back(x2, 0);
  15. }
  16.  
  17. void upd(int i, int j) {
  18. auto [x1, y1, x2, y2] = all[i];
  19. auto [x3, y3, x4, y4] = all[j];
  20. int down = min(y2, y4);
  21. int up = max(y1, y3);
  22. if (up - down < b)
  23. return;
  24. for (int z = 0; z < n; z++) {
  25. if (z != i && z != j)
  26. check(up, down, all[z]);
  27. }
  28. int cur = 0, pos = -1;
  29. sort(events.begin(), events.end());
  30. for (int i = 0, last = -1; i < events.size(); i++) {
  31. if (events[i].second) {
  32. if (cur == 0 && ans < events[i].first - last) {
  33. ans = events[i].first - last;
  34. x_ans = last;
  35. y_ans = down;
  36. }
  37. cur++;
  38. }
  39. else
  40. cur--;
  41. last = events[i].first;
  42. }
  43. events.clear();
  44. }
  45.  
  46. void Solve() {
  47. cin >> w >> h >> a >> b >> n;
  48. for (int i = 0, x1, y1, x2, y2; i < n; i++) {
  49. cin >> x1 >> y1 >> x2 >> y2;
  50. all.emplace_back(x1, y1, x2, y2);
  51. }
  52. all.emplace_back(-1, -1, 0, h + 1);
  53. all.emplace_back(-1, -1, w + 1, 0);
  54. all.emplace_back(-1, h, w + 1, h + 1);
  55. all.emplace_back(w, -1, w + 1, h + 1);
  56. n = all.size();
  57. for (int i = 0; i < n; i++)
  58. for (int j = i + 1; j < n; j++)
  59. upd(i, j);
  60. cout << x_ans << " " << y_ans << " " << x_ans + ans << " " << y_ans + b;
  61. }
  62.  
  63. int main() {
  64. ios::sync_with_stdio(false);
  65. cin.tie(nullptr);
  66. cout.tie(nullptr);
  67. Solve();
  68.  
  69. return 0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement