Submission #247013

#	Time	Username	Problem	Language	Result	Execution time	Memory
247013		dolphingarlic	Wish (LMIO19_noras)	C++14	46 / 100	307 ms	11620 KiB

noras

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    long double r;
    cin >> n >> r;
    vector<pair<ll, int>> stars;
    FOR(i, 0, n) {
        long double x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2) swap(x1, y1), swap(x2, y2);
        long double v = x2 - x1;

        long double m = (y1 - y2) / (x1 - x2);
        long double c = y1 - m * x1;
        if (m * m + c * c < 4 * (m * m + 1) * (c * c - r * r)) continue;

        long double int_1 = (-2 * m * c + 2 * sqrt(m * m * c * c -
                                              (m * m + 1) * (c * c - r * r))) /
                       (2 * m * m + 2);
        long double int_2 = (-2 * m * c - 2 * sqrt(m * m * c * c -
                                              (m * m + 1) * (c * c - r * r))) /
                       (2 * m * m + 2);
        if ((int_1 - x1) / v > (int_2 - x1) / v) swap(int_1, int_2);
        if ((int_2 - x1) / v < 0) continue;

        ll in = max(0ll, ll(ceil((int_1 - x1) / v)));
        ll out = ll(floor((int_2 - x1) / v));

        stars.push_back({in, -1});
        stars.push_back({out, 1});
    }
    sort(stars.begin(), stars.end());

    int ans = 0, cnt = 0;
    for (pair<int, int> i : stars) {
        cnt -= i.second;
        ans = max(ans, cnt);
    }
    cout << ans;
    return 0;
}

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