Submission #770888

#	Time	Username	Problem	Language	Result	Execution time	Memory
770888		dxz05	Wish (LMIO19_noras)	C++17	0 / 100	6 ms	368 KiB

noras

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 2005;

#define loop for (int it = 0; it < 200; it++)

void solve(){
    int n; ll R;
    cin >> n >> R;

    R *= R;

    long double lim = 2e5;

    vector<long double> st, en;
    set<long double> candidates;

    for (int i = 1; i <= n; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        auto dist = [&](long double t) -> long double{
            long double x = c - a, y = d - b;
            x = x * t + a;
            y = y * t + b;
            return x * x + y * y;
        };

        long double t = -1;

        long double l = 1, r = lim;
        loop{
            long double m1 = l + (r - l) / 3;
            long double m2 = r - (r - l) / 3;

            long double f1 = dist(m1), f2 = dist(m2);

            if (f1 <= R || f2 <= R){
                t = (f1 <= R ? m1 : m2);
                break;
            }

            if (f1 < f2){
                r = m2;
            } else {
                l = m1;
            }

        }

        if (t == -1) continue;

        long double _st = t, _en = t;

        l = 1, r = t;
        loop{
            long double m = (l + r) / 2;
            if (dist(m) <= R){
                _st = m;
                r = m;
            } else {
                l = m;
            }
        }

        l = t, r = lim;
        loop{
            long double m = (l + r) / 2;
            if (dist(m) <= R){
                _en = m;
                l = m;
            } else {
                r = m;
            }
        }

        assert(dist(_st) <= R && dist(_en) <= R);

        st.push_back(_st);
        en.push_back(_en);

        candidates.insert(_st);
        candidates.insert(_en);
    }

    sort(all(st));
    sort(all(en));

    int m = (int) st.size();

    int ans = 0;
    for (long double t : candidates){
        int i = upper_bound(all(st), t) - st.begin();
        int j = lower_bound(all(en), t) - en.begin() - 1;

        int cnt = m;
        cnt -= m - i;
        cnt -= j + 1;

        ans = max(ans, cnt);
    }

    cout << ans << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        //cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:124:13: warning: unused variable 'startTime' [-Wunused-variable]
  124 |     clock_t startTime = clock();
      |             ^~~~~~~~~

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