| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 716096 | tengiz05 | 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 i64 = long long;
struct Vector {
i64 x, y;
Vector(i64 x = 0, i64 y = 0) : x(x), y(y) {}
Vector operator-(Vector b) {
return Vector(x - b.x, y - b.y);
}
Vector operator+(Vector b) {
return Vector(x + b.x, y + b.y);
}
Vector operator*(i64 k) {
return Vector(x * k, y * k);
}
i64 length() {
return x * x + y * y;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
i64 R;
std::cin >> n >> R;
std::vector<Vector> a(n), b(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i].x >> a[i].y >> b[i].x >> b[i].y;
}
std::vector<std::pair<int, int>> v;
for (int i = 0; i < n; i++) {
Vector cur = a[i];
Vector delta = b[i] - a[i];
int lo = 0, hi = 1E9;
while (lo < hi) {
int m = (lo + hi + 1) / 2;
if (cur.length() >= (delta * m).length()) {
lo = m;
} else {
hi = m - 1;
}
}
Vector orig = cur;
cur = cur + delta * lo;
if (cur.length() > R * R) {
cur = cur + delta;
lo++;
}
if (cur.length() > R * R) continue;
cur = orig;
for (int j = 0; j < 20005; j++) {
if (cur.length() <= R * R) {
if (l == -1) {
l = j;
}
r = j;
}
cur = cur + delta;
}
if (l != -1) {
v.push_back({l, r});
}
}
std::vector<std::pair<int, int>> events;
for (auto [l, r] : v) {
events.emplace_back(l, 1);
events.emplace_back(r + 1, -1);
}
std::sort(events.begin(), events.end());
int k = events.size();
int cnt = 0;
int ans = 0;
for (int i = 0; i < k; ) {
int j = i;
while (j < k && events[i].first == events[j].first)
j++;
while (i < j) {
cnt += events[i].second;
i++;
}
ans = std::max(ans, cnt);
}
std::cout << ans << "\n";
return 0;
}