| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 965261 | AtabayRajabli | Wish (LMIO19_noras) | C++17 | 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>
// author : a1abay
#define all(v) v.begin(), v.end()
#define GCD(a, b) __gcd(a, b)
#define LCM(a, b) (a*b / (__gcd(a, b)))
#define int ll
typedef long long ll;
typedef long double ld;
const int inf = 1e9 + 7;
const int inff = (int)1e18 + 7;
const int sz = 2e5 + 5;
using namespace std;
int n;
ld r;
vector<array<int, 2>> v;
ld disc(ld a, ld b, ld c)
{
return b * b - 4 * a * c;
}
ld get(ld a, ld b, ld d)
{
return (-b + sqrtl(d)) / (2 * a);
}
ld get2(ld a, ld b, ld d)
{
return (-b - sqrtl(d)) / (2 * a);
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> r;
for(int i = 1; i <= n; i++)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
c -= a;
d -= b;
int ds = disc(c * c + d * d, 2 * a * c + 2 * b * d, a * a + b * b - r * r);
if(ds < 0)continue;
ld x1 = get(c * c + d * d, 2 * a * c + 2 * b * d, ds);
ld x2 = get2(c * c + d * d, 2 * a * c + 2 * b * d, ds);
if(x2 < 0LL)continue;
x1 = ceil(x1);
x2 = floor(x2);
if(x1 > x2)continue;
x1 = max(x1, 0LL);
v.push_back({(int)x1, 1});
v.push_back({(int)x2 + 1, -1});
}
int s = 0, mx = 0;
sort(all(v));
for(auto i : v)
{
s += i[1];
mx = max(mx, s);
}
cout << mx;
}