This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <math.h>
#include <stdio.h>
#define N 200000
long long max(long long a, long long b) { return a > b ? a : b; }
typedef long double ld;
typedef __int128_t L;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
long long tt[N * 2];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = tt[ii[j]] != tt[i_] ? (tt[ii[j]] < tt[i_] ? -1 : 1) : (ii[j] & 1) - (i_ & 1);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int main() {
static int ii[N * 2];
int n, n_, i, d, ans;
long long r;
scanf("%d%lld", &n, &r);
n_ = 0;
while (n--) {
long long x1, y1, x2, y2, a, b, c, t1, t2;
ld d;
scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2), x2 -= x1, y2 -= y1;
a = x2 * x2 + y2 * y2, b = (x1 * x2 + y1 * y2) * 2, c = x1 * x1 + y1 * y1 - r * r;
d = (ld) b * b - (ld) 4 * a * c;
if (d < 0)
continue;
d = sqrtl(d);
t1 = (-b - d) / 2 / a, t2 = (-b + d) / 2 / a;
while ((L) 2 * a * (t1 - 1) + b > 0 || ((L) a * (t1 - 1) + b) * (t1 - 1) + c <= 0)
t1--;
while ((L) 2 * a * t1 + b <= 0 && ((L) a * t1 + b) * t1 + c > 0)
t1++;
while ((L) 2 * a * (t2 + 1) + b <= 0 || ((L) a * (t2 + 1) + b) * (t2 + 1) + c <= 0)
t2++;
while ((L) 2 * a * t2 + b > 0 && ((L) a * t2 + b) * t2 + c > 0)
t2--;
t1 = max(t1, 0);
if (t1 <= t2)
tt[n_ << 1 | 0] = t1, tt[n_ << 1 | 1] = t2, n_++;
}
n = n_;
for (i = 0; i < n * 2; i++)
ii[i] = i;
sort(ii, 0, n * 2);
d = 0, ans = 0;
for (i = 0; i < n * 2; i++)
ans = max(ans, d += ((ii[i] & 1) == 0 ? 1 : -1));
printf("%d\n", ans);
return 0;
}
Compilation message (stderr)
noras.cpp: In function 'int main()':
noras.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d%lld", &n, &r);
| ~~~~~^~~~~~~~~~~~~~~~~~
noras.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2), x2 -= x1, y2 -= y1;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |