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>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define PB push_back
#define F first
#define S second
const int INF=1e9;
const long long LINF=1e18;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef map<int, int> mii;
const int MX=1e8, N=30000;
ll n, r;
vector<pair<pair<ll, ll>, pair<ll, ll>>> inf;
bool chk(ll x, ll y)
{
x=abs(x); y=abs(y);
if(x==r && y==0) return true;
if(y==r && x==0) return true;
if(x==0 && y==0) return true;
if(x>=0 && x<=r-1 && y>=0 && y<=r-1) return true;
else return false;
}
bool inside(ll x, ll y, ll ax, ll ay)
{
return chk(x, y)||chk(x-ax, y-ay);
}
bool passed(ll x, ll y, ll nx, ll ny)
{
bool left=false, right=false;
if(x<=0){
if(nx>=0) left=true;
}
else if(x>=0){
if(nx<=0) left=true;
}
if(x>=0 && nx>=x) left=true;
else if(x<=0 && nx<=x) left=true;
if(y>=0 && ny>=y) right=true;
else if(y<=0 && ny<=y) right=true;
if(y<=0){
if(ny>=0) right=true;
}
else if(y>=0){
if(ny<=0) right=true;
}
return left&&right;
}
const int ND=30000;
bool good(int i)
{
ll x=inf[i].F.F, y=inf[i].F.S, z=inf[i].S.F, w=inf[i].S.S;
ll ax=z-x, ay=w-y;
ll l=1, r=N;
while(l<r){
ll m=(l+r)/2;
ll nx=x+ax*m, ny=y+ay*m;
if(nx<-ND || nx>ND || ny<-ND || ny>ND) r=m;
if(passed(x, y, nx, ny)&&!chk(nx, ny)) r=m;
else l=m+1;
}
l--;
ll nx=x+l*ax, ny=y+l*ay;
if(chk(nx, ny)) return true;
return false;
}
ll times[N];
void pre(int i)
{
ll x=inf[i].F.F, y=inf[i].F.S, z=inf[i].S.F, w=inf[i].S.S;
ll ax=z-x, ay=w-y;
ll l=0, r=N;
while(l<r){
ll m=(l+r)/2;
ll nx=x+ax*m, ny=y+ay*m;
if(nx<-ND || nx>ND || ny<-ND || ny>ND) r=m;
else if(passed(x, y, nx, ny)||chk(nx, ny)) r=m;
else{
l=m+1;
}
}
times[l]++;
l=0; r=N;
while(l<r){
ll m=(l+r)/2;
ll nx=x+ax*m, ny=y+ay*m;
if(nx<-ND || nx>ND || ny<-ND || ny>ND) r=m;
else if(passed(x, y, nx, ny) && !chk(nx, ny)) r=m;
else{
l=m+1;
}
}
times[l]--;
}
int main()
{
FAST_IO;
cin >> n >> r;
vi ar;
FOR(i, 0, n)
{
ll x, y, z, w;
cin >> x >> y >> z >> w;
inf.PB({{x, y}, {z, w}});
if(inside(x, y, z-x, w-y)||good(i)){
ar.PB(i);
}
}
for(auto x : ar){
pre(x);
}
ll tot=0, mx=0;
FOR(i, 0, N)
{
tot+=times[i];
mx=max(mx, tot);
}
cout << mx;
}
# | 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... |