This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*input
2 2
3 0 5 0
-2 1 2 1
*/
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
using ll = long long;
using pll = pair<ll, ll>;
const int MAX_N = 200005;
const ll INF = 2e9;
struct Star
{
pll pos;
pll dir;
};
int N;
ll R;
Star Stars[MAX_N];
pll getNth(pll pos, pll dir, ll n)
{
if (n < 0) return {INF, INF};
return make_pair(pos.F + n * dir.F, pos.S + n * dir.S);
}
ll getINF(pll dir)
{
return INF / max(abs(dir.F), abs(dir.S));
}
ll closest(Star star)
{
ll lo = 0, hi = getINF(star.dir);
while (lo < hi)
{
ll mid = (lo + hi) / 2;
pll pos1 = getNth(star.pos, star.dir, mid);
pll pos2 = getNth(star.pos, star.dir, mid + 1);
ll d1 = pos1.F * pos1.F + pos1.S * pos1.S;
ll d2 = pos2.F * pos2.F + pos2.S * pos2.S;
if (d1 == d2)
{
return mid;
}
else if (d1 < d2)
{
hi = mid;
}
else
{
lo = mid + 1;
}
}
return lo;
}
int main()
{
scanf("%d%lld", &N, &R);
for (int i = 0; i < N; i++)
{
ll a, b, c, d;
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
Stars[i] = {{a, b}, {c - a, d - b}};
}
vector<pll> Intervals;
for (int i = 0; i < N; i++)
{
ll close = closest(Stars[i]);
pll closestPos = getNth(Stars[i].pos, Stars[i].dir, close);
if (closestPos.F * closestPos.F + closestPos.S * closestPos.S > R * R)
continue;
ll l = close, r = close;
ll did = getINF(Stars[i].dir);
for (ll step = did; step > 0; step /= 2)
{
pll pos = getNth(Stars[i].pos, Stars[i].dir, l - step);
if (pos.F * pos.F + pos.S * pos.S <= R * R)
{
l -= step;
}
}
for (ll step = did; step > 0; step /= 2)
{
pll pos = getNth(Stars[i].pos, Stars[i].dir, r + step);
if (pos.F * pos.F + pos.S * pos.S <= R * R)
{
r += step;
}
}
//cerr << l << " " << r << endl;
Intervals.push_back({l, 1});
Intervals.push_back({r + 1, -1});
}
sort(Intervals.begin(), Intervals.end());
ll best = 0;
ll curr = 0;
for (pll p : Intervals)
{
curr += p.S;
best = max(best, curr);
}
printf("%lld", best);
return 0;
}
Compilation message (stderr)
noras.cpp: In function 'int main()':
noras.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
71 | scanf("%d%lld", &N, &R);
| ~~~~~^~~~~~~~~~~~~~~~~~
noras.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
76 | scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |