Submission #1020077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020077		thinknoexit	Wish (LMIO19_noras)	C++17	100 / 100	150 ms	11712 KiB

noras

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll R;
ll x, y, sx, sy;
ll d(ll x, ll y) {
    return x * x + y * y;
}
ll val(ll k) {
    return d(sx + x * k, sy + y * k);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n >> R;
    R = R * R;
    vector<pair<ll, int>> v;
    for (int i = 1;i <= n;i++) {
        {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            x = c - a, y = d - b;
            sx = a - x, sy = b - y;
        }
        ll m;
        ll MX = 1e8 / max(abs(x), abs(y)) + 1;
        {
            ll l = 1, r = MX;
            while (l < r) {
                ll mid = (l + r + 1) / 2;
                if (val(mid) >= val(mid + 1))
                    l = mid;
                else
                    r = mid - 1;
            }
            m = l;
        }
        {
            ll l = 1, r = m + 1;
            while (l < r) {
                ll mid = (l + r) / 2;
                if (val(mid) <= R)
                    r = mid;
                else
                    l = mid + 1;
            }
            v.push_back({ l, 1 });
            //cout << l << ' ';
        }
        //cout << m << ' ';
        {
            ll l = m, r = MX;
            while (l < r) {
                ll mid = (l + r + 1) / 2;
                if (val(mid) <= R)
                    l = mid;
                else
                    r = mid - 1;
            }
            v.push_back({ l + 1, -1 });
            //cout << l << '\n';
        }
    }
    sort(v.begin(), v.end());
    int mx = 0;
    int now = 0;
    for (int i = 0, j;i < (int)v.size();i = j) {
        for (j = i;j < (int)v.size() && v[i].first == v[j].first;j++) now += v[j].second;
        mx = max(mx, now);
    }
    cout << mx;
    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 23 / 23
• Subtask 3: 15 / 15
• Subtask 4: 32 / 32
• Subtask 5: 7 / 7