제출 #247013

#제출 시각아이디문제언어결과실행 시간메모리
247013dolphingarlicWish (LMIO19_noras)C++14
46 / 100
307 ms11620 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...