Submission #377207

#TimeUsernameProblemLanguageResultExecution timeMemory
377207gustasonWish (LMIO19_noras)C++14
0 / 100
2 ms364 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; int INF = 1e9 + 5; int n, r; vector<pair<int, int>> a; vector<pair<int, int>> dir; vector<int> best; vector<pair<int, int>> fr; bool inside(int x, int y) { if (x == r && y == 0) return true; if (x == -r && y == 0) return true; if (x == 0 && y == r) return true; if (x == 0 && y == -r) return true; int rr = r; if (x >= -(rr-1) && x <= (rr-1) && y >= -(rr-1) && y <= (rr-1)) return true; return false; } int getP(int x, int x0, int d) { int ans = ceil((ld) ((ld) x - (ld) x0) / (ld) d); if (ans < 0) return -1; return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); map<int, int> mp; cin >> n >> r; a.resize(n); dir.resize(n); best.assign(n, INF); fr.resize(n); for(int i = 0; i < n; i++) { cin >> a[i].first >> a[i].second; cin >> dir[i].first >> dir[i].second; dir[i] = {dir[i].first - a[i].first, dir[i].second - a[i].second}; // cout << a[i].first << " " << a[i].second << " "; // cout << dir[i].first << " " << dir[i].second << "\n"; } cerr << "\n"; vector<pair<int, int>> ps = { {r, r}, {-r, -r}, {(r-1), (r-1)}, {-(r-1), -(r-1)} }; for(int i = 0; i < n; i++) { if (inside(a[i].first, a[i].second)) { best[i] = 0; fr[i] = a[i]; continue; } for(pair<int, int> j : ps) { int mov = getP(j.first, a[i].first, dir[i].first); // cout << a[i].first + mov * dir[i].first << " " << a[i].second + mov * dir[i].second << "\n"; if (mov != -1) { if (inside(a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second)) { if (mov < best[i]) { best[i] = mov; fr[i] = {a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second}; } } } mov = getP(j.second, a[i].second, dir[i].second); if (mov != -1) { if (inside(a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second)) { if (mov < best[i]) { best[i] = mov; fr[i] = {a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second}; } } } } } for(int i = 0; i < n; i++) { int L = best[i], R = INF, ans = INF; while(L <= R) { int mid = (L + R) / 2; if (dir[i].first != 0 && mid >= abs(INF / dir[i].first)) { R = mid - 1; ans = mid; continue; } if (dir[i].second != 0 && mid >= abs(INF / dir[i].second)) { R = mid - 1; ans = mid; continue; } if (inside(a[i].first + mid * dir[i].first, a[i].second + mid * dir[i].second)) { L = mid + 1; } else { R = mid - 1; ans = mid; } } // cerr << best[i] << " " << ans << "\n"; mp[best[i]]++; mp[ans]--; } int ans = 0, curr = 0; for(auto i : mp) { if (i.first >= INF) break; curr += i.second; ans = max(ans, curr); } cout << ans; 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...