Submission #1135914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135914		c32ardash	Wish (LMIO19_noras)	C++20	93 / 100	205 ms	5192 KiB

noras

#include <bits/stdc++.h>
#define int long long
#define double long double

using namespace std;

const int NMAX=2e5+5;
int n, r;
map<int, int> v;

/*
Delta=4R^2( (a_i-c_i)^2+(b_i-d_i)^2 ) -4(a_i_d_i-b_ic_i)^2
k_{1,2}=(-2(a_ic_i+b_id_i-a_i^2-b_i^2) \pm sqrt(Delta) ) / (2( (a_i-c_i)^2+(b_i-d_i)^2 ) )
*/
pair<int, int> secs(int a, int b, int c, int d)
{
    int dlt=r*r*((a-c)*(a-c)+(b-d)*(b-d))-(a*d-b*c)*(a*d-b*c);
    if(dlt<-1e-9)
        return {-1, -1};
    double k1=(a*a+b*b-a*c-b*d-sqrtl(dlt))/((a-c)*(a-c)+(b-d)*(b-d)),
           k2=(a*a+b*b-a*c-b*d+sqrtl(dlt))/((a-c)*(a-c)+(b-d)*(b-d));
    if(max(k1, k2)<-1e-9)
        return {-1, -1};
    return {ceil(max(min(k1, k2), (double)0)), floor(max(max(k1, k2), (double)0))};
}

signed main()
{
    cin>>n>>r;
    for(int i=1;i<=n;i++)
    {
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        pair<int, int> sus=secs(a, b, c, d);
        if(sus.second!=-1)
        {
            v[sus.first]++;
            v[sus.second+1]--;
        }
    }
    int ans=0, cnt=0;
    for(auto x:v)
    {
        cnt+=x.second;
        ans=max(ans, cnt);
    }
    cout<<ans;
    return 0;
}

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