Advertisement
Guest User

Untitled

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