| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 213066 | qkxwsm | Wish (LMIO19_noras) | C++14 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef __int128_t ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pll, pll> ppp;
const int MAXN = 200013;
int N;
ll R;
int ans;
map<ll, int> pref;
ll fdiv(ll a, ll b)
{
return a / b - (a % b < 0);
}
ll cdiv(ll a, ll b)
{
return a / b + (a % b > 0);
}
int32_t main()
{
cout << fixed << setprecision(12);
cerr << fixed << setprecision(4);
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N;
long long rr; cin >> rr; R = rr;
FOR(i, 0, N)
{
long long A, B, C, D;
cin >> A >> B >> C >> D;
ll a, b, c, d;
a = A; b = B; c = C; d = D;
c -= a; d -= b;
ll r = c * c + d * d;
ll s = 2 * b * d + 2 * a * c;
ll t = a * a + b * b - R * R;
// cerr << r << ' ' << s << ' ' << t << endl;
if (s * s - 4 * r * t < 0) continue;
ll sq = sqrt(s * s - 4 * r * t) + 2;
while(sq * sq > s * s - 4 * r * t) sq--;
// cerr << -s-sq << ' ' << -s + sq << ' ' << 2 * r << endl;
ll lo = cdiv(-s - sq, 2 * r), hi = fdiv(-s + sq, 2 * r);
// cerr << lo << '@' << hi << endl;
ckmax(lo, 0);
if (lo > hi) continue;
// cerr << lo << ',' << hi << endl;
pref[lo]++; pref[hi + 1]--;
}
if (pref.empty())
{
cout << "0\n";
return 0;
}
for (auto it = next(pref.begin()); it != pref.end(); it++)
{
it -> se += (prev(it)) -> se;
}
for (auto p : pref)
{
ckmax(ans, p.se);
}
cout << ans << '\n';
return 0;
}