Submission #465532

#TimeUsernameProblemLanguageResultExecution timeMemory
465532idasWish (LMIO19_noras)C++11
0 / 100
1 ms332 KiB
#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=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; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...