Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <utility>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct rect {
- pair<int, int> dot[2];
- rect() {}
- rect(int x1, int y1, int x2, int y2) {
- dot[0].first = min(x1, x2);
- dot[0].second = max(y1, y2);
- dot[1].first = max(x1, x2);
- dot[1].second = min(y1, y2);
- }
- };
- double get_k(pair<int, int> x) {
- if (x.first == 0) return INT_MAX;
- return 1.0 * x.second / x.first;
- }
- int main(){
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- freopen("rect.in", "r", stdin);
- freopen("rect.out", "w", stdout);
- int n, xmax, ymax;
- cin >> xmax >> ymax >> n;
- rect data[10019];
- int x1, y1, x2, y2;
- for (int i = 0; i < n; i++) {
- cin >> x1 >> y1 >> x2 >> y2;
- data[i] = rect(x1, y1, x2, y2);
- }
- vector<pair<double, int>> tmp;
- for (int i = 0; i < n; i++) {
- tmp.emplace_back(get_k(data[i].dot[0]), -1);
- tmp.emplace_back(get_k(data[i].dot[1]), 1);
- }
- sort(tmp.begin(), tmp.end());
- int best_ind = -1, now = 0, res = 0;
- for (int i = 0; i < (int) tmp.size(); i++) {
- now += tmp[i].second;
- if (now > res) {
- res = now;
- best_ind = i;
- }
- }
- cout << res << ' ';
- double rr = (best_ind < 2*n ? tmp[best_ind + 1].first : 1.0 * INT_MAX), ll = tmp[best_ind].first;
- double tmp_k = get_k(make_pair(xmax, ymax));
- if (tmp_k <= rr && tmp_k >= ll) cout << xmax << ' ' << ymax;
- else {
- if (tmp_k < ll) {
- // ymax;
- int l = -1, r = xmax;
- while (r - l > 1) {
- int m = (l + r) / 2;
- double tmp = get_k(make_pair(m, ymax));
- if (tmp > rr) l = m;
- else r = m;
- }
- cout << r << ' ' << ymax;
- } else {
- // xmax
- int l = 0, r = ymax + 1;
- while (r - l > 1) {
- int m = (l + r) / 2;
- double tmp = get_k(make_pair(xmax, m));
- if (tmp > rr) r = m;
- else l = m;
- }
- cout << xmax << ' ' << l;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement