Submission #1164834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164834		AbdullahIshfaq	Wish (LMIO19_noras)	C++20	93 / 100	81 ms	5188 KiB

noras

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
ll n, r;
map<ll, ll> mp;
pair<ll, ll> tme(ll a, ll b, ll c, ll d){

	// dx = abs(a - c), dy = (b - d)
	// => equ = (x + dx * t) ^ 2 + (y + dy * t) ^ 2 <= r ^ 2;
	// => (t * dx) ^ 2 + (t * dy) ^ 2 + 2 * x * t * dx + 2 * y * t * dy + x ^ 2 + y ^ 2 - r ^ 2 <= 0
	// => quadratic equation
	// => a = (t * dx) ^ 2 + (t * dy) ^ 2
	// => b = 2 * x * t * dx + 2 * y * t * dy
	// => c = x ^ 2 + y ^ 2 - r ^ 2
	ll dx = a - c, dy = b - d;
	ll dlt = (a * dx + b * dy) * (a * dx + b * dy) - ((dx * dx + dy * dy) * (a * a + b * b - r * r));
    if(dlt < 0){
    	return {-1, -1};
	}
    long double in = (a * dx + b * dy - sqrtl(dlt)) / (dx * dx + dy * dy), out = (a * dx + b * dy + sqrtl(dlt)) / (dx * dx + dy * dy);
    if(max(in, out) < -1e-7){
        return {-1, -1};
	}
	return {ceil(max(min(in, out), (long double)0)), floor(max(max(in, out), (long double)0))};
}
void solve(){
	cin >> n >> r;
    for(int i = 1; i <= n; i++){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        auto tmp = tme(a, b, c, d);
        if(tmp.first != -1){
            mp[tmp.first]++;
            mp[tmp.second + 1]--;
        }
    }
    ll ans = 0, c = 0;
    for(auto i : mp){
        c += i.second;
        ans = max(ans, c);
    }
    cout << ans << '\n';
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for(int i = 1; i <= tests; i ++)
		solve();
}

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