| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1023563 | vjudge1 | Wish (LMIO19_noras) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n; long long r;
cin >> n >> r;
vector<long long> a(n), b(n), c(n), d(n);
for (int i=0; i<n; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
vector<pair<long long, bool>> evs;
for (int i=0; i<n; i++) {
// p(t) = (a[i] + t * dx, b[i] + t * dy)
// cari t sehingga (a[i] + t * dx)^2 + (b[i] + t * dy)^2 = r^2
// => a[i]^2 + t^2*dx^2 + 2*t*a[i]*dx + b[i]^2 + t^2*dy^2 + 2*t*b[i]*dy = r^2
// => t^2 * (dx^2 + dy^2) + t * (2*a[i]*dx + 2*b[i]*dy) + a[i]^2 + b[i]^2 - r^2 = 0
// => t^2 * A + t * B + C = 0
// pakai rumus akar persamaan kuadrat?
__int128_t dx = c[i] - a[i], dy = d[i] - b[i];
__int128_t A = dx * dx + dy * dy, B = 2 * (a[i] * dx + b[i] * dy), C = a[i] * a[i] + b[i] * b[i] - r * r;
__int128_t D = B * B - 4 * A * C;
if (D >= 0) {
long double sd = sqrt(D);
long double t1 = (-B + sd) / (2 * A);
long double t2 = (-B - sd) / (2 * A);
long long llt1 = ceil(min(t1, t2));
long long llt2 = floor(max(t1, t2));
if (llt1 <= llt2) {
evs.emplace_back(llt1, 0);
evs.emplace_back(llt2, 1);
}
}
}
sort(evs.begin(), evs.end());
int ans = 0, cnt = 0;
for (int i=0; i<(int)evs.size(); i++) {
auto &[t, rem] = evs[i];
if (t >= 0) ans = max(ans, cnt);
if (rem) {
cnt--;
} else {
cnt++;
}
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int tcs = 1;
// cin >> tcs;
while (tcs--) {
solve();
}
return 0;
}