| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1016059 |
2024-07-07T10:52:02 Z |
BuzzyBeez |
Wish (LMIO19_noras) |
C++17 |
|
1 ms |
2396 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
