Submission #253296

#	Time	Username	Problem	Language	Result	Execution time	Memory
253296		DystoriaX	Wish (LMIO19_noras)	C++14	100 / 100	142 ms	11360 KiB

noras

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, int> pii;

int n, r;
int a[200010], b[200010], dx[200010], dy[200010];
int pref[200010];

vector<pii> v;

long long sq(long long x){
	return x * x;
}

bool check(long long dx, long long dy){
	return sq(dx) + sq(dy) <= sq(r);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> r;

	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i] >> dx[i] >> dy[i];
		
		dx[i] -= a[i];
		dy[i] -= b[i];

		long long A, B, C;
		long double D;

		A = sq(dx[i]) + sq(dy[i]); B = 2LL * (1LL * a[i] * dx[i] + 1LL * b[i] * dy[i]); C = sq(a[i]) + sq(b[i]) - sq(r);

		D = (long double) B*B - (long double) 4 * A * C;

		// cerr << mn << " " << mx << "\n";
		if(D < 0) continue;

		long long mn = ceil((long double) (-B - sqrtl(D)) / (2LL * A)), mx = floor((long double) (-B + sqrtl(D)) / (2LL * A));

		bool f1, f2;

		for(int off = -10; off <= 10; off++){
			if(check(a[i] + 1LL * (mn + off) * dx[i], b[i] + 1LL * (mn + off) * dy[i])){
				mn += off; f1 = true;
				break;
			}
		}

		for(int off = 10; off >= -10; off--){
			if(check(a[i] + 1LL * (mx + off) * dx[i], b[i] + 1LL * (mx + off) * dy[i])){
				mx += off; f2 = true;
				break;
			}
		}

		if(!f1 || !f2) continue;

		if(mx >= 0 && mn <= mx){
			// cerr << mn << " " << mx << "\n";
			assert(check(a[i] + 1LL * mn * dx[i], b[i] + 1LL * mn * dy[i]));
			assert(check(a[i] + 1LL * mx * dx[i], b[i] + 1LL * mx * dy[i]));
			v.emplace_back(max(0LL, mn), 1);
			v.emplace_back(mx + 1, -1);
		}
		// for(int k = 0; k <= 20000; k++){
		// 	if(sq(a[i] + 1LL * k * dx[i]) + sq(b[i] + 1LL * k * dy[i]) <= sq(r)) pref[k]++;
		// }
	}

	int ans = 0, cnt = 0;

	sort(v.begin(), v.end());

	for(int i = 0; i < (int) v.size(); i++){
		int j = i;

		while(j < (int) v.size() && v[i].first == v[j].first){
			cnt += v[j++].second;
		}

		ans = max(ans, cnt);
		i = j - 1;
	}

	cout << ans << "\n";
	
	return 0;
}

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