Submission #1016059

#TimeUsernameProblemLanguageResultExecution timeMemory
1016059BuzzyBeezWish (LMIO19_noras)C++17
0 / 100
1 ms2396 KiB
#include <bits/stdc++.h> using namespace std; #define big __int128_t const long double eps = 1e-12; const long long inf = 1LL << 60; const long long lim = 1e9; long long R, sx, sy, sx2, sy2, vx, vy, l, r; big X, Y, Z, T; bool check(long long a) { // is it in the circle if (a < 0) return 0; if (a > lim) return 0; return (sx + a * vx) * (sx + a * vx) + (sy + a * vy) * (sy + a * vy) <= R * R; } pair<long long, long long> p[200008]; vector<long long> tbc; void compress() {sort(tbc.begin(), tbc.end()); tbc.resize(unique(tbc.begin(), tbc.end()) - tbc.begin());} int order(long long key) {return lower_bound(tbc.begin(), tbc.end(), key) - tbc.begin() + 1;} int upd[400008]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, ans = 0, m = 0; cin >> n >> R; pair<long long, long long> range; for (int i = 1; i <= n; ++i) { cin >> sx >> sy >> sx2 >> sy2; vx = sx2 - sx; vy = sy2 - sy; X = vx * vx + vy * vy; Y = 2 * (sx * vx + sy * vy); Z = R * R - sx * sx - sy * sy; T = 4 * X * Z + Y * Y; if (T < 0) continue; l = (-Y - sqrtl(T)) / (2 * X); r = (-Y + sqrtl(T)) / (2 * X); range = {1, -1}; for (long long i = l - 50; i <= l + 50; ++i) if (check(i)) {range.first = i; break;} for (long long i = r + 50; i >= r - 50; --i) if (check(i)) {range.second = i; break;} // cout << i << ' ' << range.first << ' ' << range.second << '\n'; // cout << X << ' ' << Y << ' ' << Z << ' ' << T << ' ' << l << ' ' << r << '\n'; if (range.first <= range.second) { p[++m] = range; tbc.push_back(range.first); tbc.push_back(range.second); } } compress(); for (int i = 1; i <= m; ++i) p[i].first = order(p[i].first), p[i].second = order(p[i].second); for (int i = 1; i <= m; ++i) ++upd[p[i].first], --upd[p[i].second + 1]; for (int i = 1; i <= tbc.size() + 1; ++i) upd[i] += upd[i - 1]; ans += *max_element(upd + 1, upd + tbc.size() + 1); cout << ans; }

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 1; i <= tbc.size() + 1; ++i) upd[i] += upd[i - 1];
      |                  ~~^~~~~~~~~~~~~~~~~
#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...