Advertisement
Guest User

Untitled

a guest
Feb 17th, 2020
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.30 KB | None | 0 0
  1. #include <iostream>
  2. #include <utility>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. struct rect {
  9.     pair<int, int> dot[2];
  10.  
  11.     rect() {}
  12.  
  13.     rect(int x1, int y1, int x2, int y2) {
  14.         dot[0].first = min(x1, x2);
  15.         dot[0].second = max(y1, y2);
  16.         dot[1].first = max(x1, x2);
  17.         dot[1].second = min(y1, y2);
  18.     }
  19. };
  20.  
  21. double get_k(pair<int, int> x) {
  22.     if (x.first == 0) return INT_MAX;
  23.     return 1.0 * x.second / x.first;
  24. }
  25.  
  26. int main(){
  27.     ios_base::sync_with_stdio(false);
  28.     cin.tie(0);
  29.     cout.tie(0);
  30. //    freopen("input.txt", "r", stdin);
  31. //    freopen("output.txt", "w", stdout);
  32.     freopen("rect.in", "r", stdin);
  33.     freopen("rect.out", "w", stdout);
  34.     int n, xmax, ymax;
  35.     cin >> xmax >> ymax >> n;
  36.     rect data[10019];
  37.     int x1, y1, x2, y2;
  38.     for (int i = 0; i < n; i++) {
  39.         cin >> x1 >> y1 >> x2 >> y2;
  40.         data[i] = rect(x1, y1, x2, y2);
  41.     }
  42.     vector<pair<double, int>> tmp;
  43.     for (int i = 0; i < n; i++) {
  44.         tmp.emplace_back(get_k(data[i].dot[0]), -1);
  45.         tmp.emplace_back(get_k(data[i].dot[1]), 1);
  46.     }
  47.     sort(tmp.begin(), tmp.end());
  48.     int best_ind = -1, now = 0, res = 0;
  49.     for (int i = 0; i < (int) tmp.size(); i++) {
  50.         now += tmp[i].second;
  51.         if (now > res) {
  52.             res = now;
  53.             best_ind = i;
  54.         }
  55.     }
  56.     cout << res << ' ';
  57.     double rr = (best_ind < 2*n ? tmp[best_ind + 1].first : 1.0 * INT_MAX), ll = tmp[best_ind].first;
  58.     double tmp_k = get_k(make_pair(xmax, ymax));
  59.     if (tmp_k <= rr && tmp_k >= ll) cout << xmax << ' ' << ymax;
  60.     else {
  61.         if (tmp_k < ll) {
  62.             // ymax;
  63.             int l = -1, r = xmax;
  64.             while (r - l > 1) {
  65.                 int m = (l + r) / 2;
  66.                 double tmp = get_k(make_pair(m, ymax));
  67.                 if (tmp > rr) l = m;
  68.                 else r = m;
  69.             }
  70.             cout << r << ' ' << ymax;
  71.         } else {
  72.             // xmax
  73.             int l = 0, r = ymax + 1;
  74.             while (r - l > 1) {
  75.                 int m = (l + r) / 2;
  76.                 double tmp = get_k(make_pair(xmax, m));
  77.                 if (tmp > rr) r = m;
  78.                 else l = m;
  79.             }
  80.             cout << xmax << ' ' << l;
  81.         }
  82.     }
  83.  
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement