Submission #1350572

#TimeUsernameProblemLanguageResultExecution timeMemory
1350572Faisal_SaqibWish (LMIO19_noras)C++20
100 / 100
100 ms11100 KiB
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define ld long double
#define pl pair<ll,ll>
#define x first
#define y second
const ll N=5e5+10;
pl f[N],s[N],inc[N];
ll n,r;
void solve()
{
    cin>>n>>r;
    map<ll,ll> dif;
    ll always=0;
    const ld eps=1e-12L;
    for(int i=1;i<=n;i++)
    {
        cin>>f[i].x>>f[i].y>>s[i].x>>s[i].y;
        inc[i].x=(s[i].x-f[i].x);
        inc[i].y=(s[i].y-f[i].y);
        ll A=inc[i].x*inc[i].x+inc[i].y*inc[i].y;
        ll B=f[i].x*inc[i].x+f[i].y*inc[i].y;
        B=2*B;
        ll C=f[i].x*f[i].x+f[i].y*f[i].y-r*r;
        if(A==0)
        {
            if(C<=0)
                always++;
            continue;
        }
        __int128 D=(__int128)B*B-(__int128)4*A*C;
        if(D<0)
            continue;
        ld sq=sqrtl((ld)D);
        ld lroot=((ld)-B-sq)/((ld)2*A);
        ld rroot=((ld)-B+sq)/((ld)2*A);
        if(rroot<lroot)
            swap(lroot,rroot);
        ll rl=(ll)ceill(lroot-eps);
        ll rr=(ll)floorl(rroot+eps);
        rr=max(rr,(ll)-1);
        rl=max(rl,(ll)0);
        auto inside=[&](ll t)->bool
        {
            __int128 val=(__int128)A*t*t+(__int128)B*t+C;
            return val<=0;
        };
        while(rl<=rr && !inside(rl))
            rl++;
        while(rl<=rr && !inside(rr))
            rr--;
        if(rl<=rr)
        {
            dif[rl]++;
            dif[rr+1]--;
        }
    }
    ll pr=always;
    ll mx=always;
    for(auto it:dif)
    {
        pr+=it.second;
        mx=max(mx,pr);
    }
    cout<<mx<<endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--)solve();
    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...