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 <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<long long, long long> pii;
const int MAXN = 2e5 + 5;
const ll INF = (1LL << 60) + 5;
const ll INF_binary = (1 << 30);
int n;
ll R;
vector<pii> dogadaji;
double udaljenost(pii T) { return sqrt((double)T.X * T.X + (double)T.Y * T.Y); }
pii izracunaj_tocku(ll x, ll y, ll sx, ll sy, ll t) {
ll x2 = min(INF, x + t * sx);
ll y2 = min(INF, y + t * sy);
// cerr << x2 << ' ' << y2 << '\n';
return {x2, y2};
}
void dodaj_tocku() {
ll x, y, sx, sy;
cin >> x >> y >> sx >> sy;
sx -= x;
sy -= y;
// cerr << '\n' << x << ' ' << y << " : " << sx << ' ' << sy << '\n';
ll l = 0, r = INF_binary, m1, m2;
while (r - l >= 3) {
m1 = l + (r - l) / 3;
m2 = r - (r - l) / 3;
double d1 = udaljenost(izracunaj_tocku(x, y, sx, sy, m1));
double d2 = udaljenost(izracunaj_tocku(x, y, sx, sy, m2));
// cerr << l << ' ' << r << " : " << m1 << ' ' << m2 << " : " << d1 << ' '
// << d2 << '\n';
if (d1 < d2)
r = m2;
else
l = m1;
}
for (int i = l + 1; i <= r; i++) {
if (udaljenost(izracunaj_tocku(x, y, sx, sy, l)) >
udaljenost(izracunaj_tocku(x, y, sx, sy, i)))
l = i;
}
pii sredina = izracunaj_tocku(x, y, sx, sy, l);
ll xx = sredina.X;
ll yy = sredina.Y;
// cerr << "sredina " << l << " : " << xx << ' ' << yy;
// cerr << " : " << udaljenost({xx, yy}) << ' ' << r << '\n';
if (udaljenost({xx, yy}) > R)
return;
ll lo = 0, hi = l, mid;
while (lo < hi) {
mid = (lo + hi) / 2;
double d = udaljenost(izracunaj_tocku(x, y, sx, sy, mid));
// cerr << lo << ' ' << hi << " : " << mid << ' ' << d << ' ' << R << '\n';
if (d <= R)
hi = mid;
else
lo = mid + 1;
}
ll t1 = lo;
lo = l, hi = INF_binary;
while (lo < hi) {
mid = (lo + hi) / 2 + 1;
double d = udaljenost(izracunaj_tocku(x, y, sx, sy, mid));
if (d <= R)
lo = mid;
else
hi = mid - 1;
}
ll t2 = lo;
// cerr << t1 << ' ' << t2 << '\n';
dogadaji.push_back({t1 * 2, +1});
dogadaji.push_back({t2 * 2 + 1, -1});
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> R;
for (int i = 0; i < n; i++) {
dodaj_tocku();
}
int maks = 0;
int trenutno = 0;
sort(dogadaji.begin(), dogadaji.end());
// cerr << '\n';
for (auto nx : dogadaji) {
trenutno += nx.Y;
maks = max(maks, trenutno);
}
cout << maks << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |