Submission #199922

#	Time	Username	Problem	Language	Result	Execution time	Memory
199922		SamAnd	Wish (LMIO19_noras)	C++17	0 / 100	6 ms	504 KiB

noras

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
struct ban
{
    long long x;
    int z;
    ban(){}
    ban(long long x, int z)
    {
        this->x = x;
        this->z = z;
    }
};
bool operator<(const ban& a, const ban& b)
{
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    return a.z < b.z;
}

int n;
long double R;
long double a[N], b[N], c[N], d[N];

long long l[N], r[N];

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >> R;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        c[i] -= a[i];
        d[i] -= b[i];
        long double aa = c[i] * c[i] + d[i] * d[i];
        long double bb = 2 * a[i] * c[i] + 2 * b[i] * d[i];
        long double cc = a[i] * a[i] + b[i] * b[i] - R * R;
        long double D = bb * bb - 4 * aa * cc;
        if (D < 0)
            continue;
        long double ll = (-sqrt(D) - bb) / (2 * aa);
        long double rr = (sqrt(D) - bb) / (2 * aa);
        if (ll > 0)
        {
            l[i] = ll;
            if (ll != l[i])
                ++l[i];
        }
        if (rr >= 0)
        {
            r[i] = rr;
        }
        else
        {
            r[i] = -1;
        }
    }
    vector<ban> v;
    for (int i = 1; i <= n; ++i)
    {
        v.push_back(ban(l[i], 1));
        v.push_back(ban(r[i] + 1, -1));
    }
    sort(v.begin(), v.end());
    int ans = 0;
    int yans = 0;
    for (int i = 0; i < v.size(); ++i)
    {
        yans += v[i].z;
        ans = max(ans, yans);
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~

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