oj.uz

Submission #199922

# Submission time Handle Problem Language Result Execution time Memory
199922 2020-02-04T05:31:14 Z SamAnd Wish (LMIO19_noras) C++17
0 / 100
 6 ms 504 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 6 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 6 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 6 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 6 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 6 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -