Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <utility>
- #include <vector>
- #include <algorithm>
- #include <climits>
- 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);
- }
- tmp.push_back(make_pair(0, 0));
- sort(tmp.begin(), tmp.end(), [](pair<double, int> left, pair<double, int> right) {
- if (abs(left.first - right.first) < 1e-10) return left.second > right.second;
- return left.first < right.first;
- } );
- int now = 0, res = 0;
- pair<int, int> dot = make_pair(0, 0);
- for (int i = 1; i < (int) tmp.size(); i++) {
- double rr = tmp[i].first, ll = tmp[i - 1].first;
- double tmp_k = get_k(make_pair(xmax, ymax));
- if (tmp_k <= rr && tmp_k >= ll) {
- if (now > res) {
- res = now;
- dot = make_pair(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;
- }
- if (ll <= get_k(make_pair(r, ymax)) && get_k(make_pair(r, ymax)) <= rr && now > res) {
- res = now;
- dot = make_pair(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;
- }
- if (ll <= get_k(make_pair(xmax, l)) && get_k(make_pair(xmax, l)) <= rr && now > res) {
- res = now;
- dot = make_pair(xmax, l);
- }
- }
- }
- now += tmp[i].second;
- }
- cout << res << ' ' << dot.first << ' ' << dot.second;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement