#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using pf32 = pair<float, float>;
using pf64 = pair<double, double>;
using pf80 = pair<long double, long double>;
using vf32 = vector<float>;
using vf64 = vector<double>;
using vf80 = vector<long double>;
using vpf32 = vector<pf32>;
using vpf64 = vector<pf64>;
using vpf80 = vector<pf80>;
using vvf32 = vector<vf32>;
using vvf64 = vector<vf64>;
using vvf80 = vector<vf80>;
using vvpf32 = vector<vpf32>;
using vvpf64 = vector<vpf64>;
using vvpf80 = vector<vpf80>;
template <typename key, typename val>
using ord_map = tree<key, val, less<key>, rb_tree_tag,
tree_order_statistics_node_update>;
template <typename key>
using ord_set = tree<key, null_type, less<key>, rb_tree_tag,
tree_order_statistics_node_update>;
const int BUF_SZ = 1 << 15;
inline namespace fast_in
{
char buf[BUF_SZ];
int pos;
int len;
char next_char(FILE *f)
{
if (pos == len)
{
pos = 0;
len = (int)fread(buf, 1, BUF_SZ, f);
if (!len)
{
return EOF;
}
}
return buf[pos++];
}
int read_int(FILE *f)
{
int x;
char ch;
int sgn = 1;
while (!isdigit(ch = next_char(f)))
{
if (ch == '-')
{
sgn *= -1;
}
}
x = ch - '0';
while (isdigit(ch = next_char(f)))
{
x = x * 10 + (ch - '0');
}
return x * sgn;
}
}
/**
* @brief gale programos flush_out kviest!!
*/
inline namespace fast_out
{
char buf[BUF_SZ];
int pos;
void flush_out(FILE *f)
{
fwrite(buf, 1, pos, f);
pos = 0;
}
void write_char(char c, FILE *f)
{
if (pos == BUF_SZ)
{
flush_out(f);
}
buf[pos++] = c;
}
void write_int(int x, FILE *f)
{
static char num_buf[100];
if (x < 0)
{
write_char('-', f);
x *= -1;
}
int len = 0;
for (; x >= 10; x /= 10)
{
num_buf[len++] = (char)('0' + (x % 10));
}
write_char((char)('0' + x), f);
while (len)
{
write_char(num_buf[--len], f);
}
write_char('\n', f);
}
}
#pragma endregion
__int128_t mult(int64_t a, int64_t b)
{
return __int128_t(a) * b;
}
__int128_t square(int64_t a)
{
return mult(a, a);
}
struct func_t
{
__int128_t a, b, c;
func_t(p64 star, p64 speed)
{
a = square(speed.first) + square(speed.second);
b = 2 * (mult(star.first, speed.first) + mult(star.second, speed.second));
c = square(star.first) + square(star.second);
}
__int128_t eval(int64_t x)
{
return a * x * x + b * x + c;
}
};
bool point_in_circle(p64 p, int64_t radius)
{
__int128_t x = square(p.first);
__int128_t y = square(p.second);
__int128_t r = square(radius);
return x + y <= r;
}
int64_t find_peak(func_t func, int64_t right = 1e9 + 1)
{
int64_t l = -1, r = right;
while (r - l > 1)
{
int64_t mid = (l + r) >> 1;
if (func.eval(mid) < func.eval(mid + 1))
{
r = mid;
}
else
{
l = mid + 1;
}
}
return l + 1;
}
int64_t find_bound(int64_t peak, int64_t radius, func_t func,
bool decrease, int upper = 1e9 + 1)
{
if (func.eval(peak) > radius * radius)
{
return -1;
}
int mult = decrease ? -1 : 1;
int64_t res = 0;
for (int64_t index = 30; index >= 0; index--)
{
int64_t cur = peak + mult * (res + (1 << index));
if (cur < 0 || cur > upper)
{
continue;
}
__int128_t val = func.eval(cur);
if (val > radius * radius)
{
continue;
}
res += 1 << index;
}
return peak + mult * res;
}
p64 find_range(p64 star, p64 speed, int64_t radius)
{
func_t distance(star, speed);
// int64_t peak = find_peak(distance);
int64_t peak_l = find_peak(distance);
int64_t peak_r = peak_l + 1;
peak_l = clamp(peak_l, int64_t(0), int64_t(1e9 + 1));
peak_r = clamp(peak_l, int64_t(0), int64_t(1e9 + 1));
int64_t left = find_bound(peak_l, radius, distance, true);
int64_t right = find_bound(peak_r, radius, distance, false);
if (left == right && right == -1)
{
return {-1, -1};
}
assert(left != -1 && right != -1);
return {left, right};
}
int main()
{
#ifndef _AAAAAAAAA
ios_base::sync_with_stdio(false);
cin.tie(0);
#else
freopen("noras.in", "r", stdin);
#ifndef __linux__
atexit([]()
{
freopen("con", "r", stdin);
system("pause"); });
#endif
#endif
int64_t n, radius;
cin >> n >> radius;
vp64 star(n),
speed(n);
for (int i = 0; i < n; i++)
{
int64_t a, b, c, d;
cin >> a >> b >> c >> d;
star[i] = {a, b};
speed[i] = {c - a, d - b};
}
vp64 ranges;
for (size_t i = 0; i < n; i++)
{
p64 time = find_range(star[i], speed[i], radius);
if (time == make_pair<int64_t, int64_t>(-1, -1))
{
continue;
}
ranges.emplace_back(time.first, 1);
ranges.emplace_back(time.second, -1);
}
sort(ranges.begin(), ranges.end(),
[](p64 a, p64 b)
{
return (a.first == b.first) ? a.second > b.second : a.first < b.first;
});
int64_t count = 0;
int64_t result = 0;
for (auto &r : ranges)
{
count += r.second;
result = max(count, result);
}
cout << result << '\n';
return 0;
}
Compilation message
noras.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
8 | #pragma region dalykai
|
noras.cpp:151: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
151 | #pragma endregion
|
noras.cpp: In function 'int main()':
noras.cpp:293:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
293 | for (size_t i = 0; i < n; i++)
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
