Submission #253190

#TimeUsernameProblemLanguageResultExecution timeMemory
253190DystoriaXWish (LMIO19_noras)C++14
0 / 100
1 ms384 KiB
#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; } long long sqDist(long long dx, long long dy){ return sq(dx) + sq(dy); } bool check(long long dx, long long dy){ return sqDist(dx, dy) <= sq(r); } bool check(long long d){ return d <= sq(r); } long long TernarySearch(int a, int b, int dx, int dy){ long long l, r, tp, ret; l = ceil((2e8 - a) / abs(dx)), r = ceil((2e8 - b) / abs(dy)); r = min(l, r); l = 0; if(r < 0) return -1; tp = 4e18; ret = -1; while(l <= r){ long long m1, m2, v1, v2; m1 = l + (r - l) / 3; m2 = r - (r - l) / 3; v1 = sqDist(a + 1LL * m1 * dx, b + 1LL * m1 * dy); v2 = sqDist(a + 1LL * m2 * dx, b + 1LL * m2 * dy); if(v1 > v2){ l = m1 + 1; if(tp > v2){ ret = m2; tp = v2; } } else { r = m2 - 1; if(tp > v1){ ret = m1; tp = v1; } } } if(check(tp)) return ret; else return -1; } long long SearchLeft(int a, int b, int dx, int dy, long long pvt){ long long l, r; l = 0; r = pvt; while(l <= r){ long long m = (l + r) >> 1; if(check(a + 1LL * m * dx, b + 1LL * m * dy)) r = m - 1; else l = m + 1; } return l; } long long SearchRight(int a, int b, int dx, int dy, long long pvt){ long long l, r; l = ceil((2e8 - a) / abs(dx)), r = ceil((2e8 - b) / abs(dy)); r = min(l, r); l = pvt; while(l <= r){ long long m = (l + r) >> 1; if(check(a + 1LL * m * dx, b + 1LL * m * dy)) l = m + 1; else r = m - 1; } return 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 mn, mx, pvt; pvt = TernarySearch(a[i], b[i], dx[i], dy[i]); // cerr << i << ":\n"; // cerr << pvt << "\n"; if(pvt == -1) continue; mn = SearchLeft(a[i], b[i], dx[i], dy[i], pvt); mx = SearchRight(a[i], b[i], dx[i], dy[i], pvt); if(mn > mx) swap(mn, mx); // cerr << mn << " " << mx << "\n"; 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; }
#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...