제출 #1135906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135906		c32ardash	Wish (LMIO19_noras)	C++17	0 / 100	1 ms	328 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<0)
    return {-1, -1};
    double k1=(a*a+b*b-a*c-b*d-sqrt(dlt))/((a-c)*(a-c)+(b-d)*(b-d)),
           k2=(a*a+b*b-a*c-b*d+sqrt(dlt))/((a-c)*(a-c)+(b-d)*(b-d));
    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>0)
        {
            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: 0 / 23
• Subtask 2: 0 / 23
• Subtask 3: 0 / 15
• Subtask 4: 0 / 32
• Subtask 5: 0 / 7