제출 #1339214

#제출 시각아이디문제언어결과실행 시간메모리
1339214haroldasWish (LMIO19_noras)C++20
93 / 100
100 ms15572 KiB
/*
    Problem link: https://oj.uz/problem/view/LMIO19_noras
    Tags: 
*/

#include<bits/stdc++.h>

using namespace std;

//#define MULTI
#define ll long long
#define all(x) (x).begin(), (x).end()

void solve() {
    ll n, r;
    cin >> n >> r;
    vector<vector<ll>> pos(n, vector<ll>(4));
    map<ll, ll> times;
    for (int i = 0; i < n; i++)
    {
        cin >> pos[i][0] >> pos[i][1] >> pos[i][2] >> pos[i][3];
        ll kx = pos[i][2]-pos[i][0];
        ll ky = pos[i][3]-pos[i][1];
        ll a = (kx*kx) + (ky*ky);
        ll b = (kx*pos[i][0] + ky*pos[i][1]);
        ll c = (pos[i][0]*pos[i][0]) + (pos[i][1]*pos[i][1]) - (r*r);
        ll D = (b*b) - a*c;
        if(D < 0) continue;
        ll t1 = ceil((-b - sqrtl(D))/a);
        ll t2 = floor((-b + sqrtl(D))/a);
        if(t2 < 0 || t2 < t1) continue;
        times[max(t1, 0ll)]++;
        times[t2+1]--;
    }
    ll mx = 0, cur = 0;
    for(auto i: times) {
        cur += i.second;
        mx = max(mx, cur);
    }
    cout << mx << "\n";
}

int main(int argc, char **argv)
{    
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef MULTI
        int t;
        cin >> t;
        while (t--)
        {
            solve();   
        }
    #else
        solve();
    #endif
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...