Submission #626594

#TimeUsernameProblemLanguageResultExecution timeMemory
626594mkisicWish (LMIO19_noras)C++14
100 / 100
508 ms8756 KiB
#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 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...