Submission #1249022

#TimeUsernameProblemLanguageResultExecution timeMemory
1249022PokemonMasterMobile (BOI12_mobile)C++20
0 / 100
579 ms35680 KiB
#include<bits/stdc++.h> using namespace std; #define double long double double equ(double x1,double y1,double x2,double y2) { return (x1*x1+y1*y1-(x2*x2+y2*y2))/(2.0*(x1-x2)); } double dist(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } signed main() { int n,l; cin>>n>>l; vector <double> x(n+1); vector <double> y(n+1); for(int i=1;i<=n;i++)cin>>x[i]>>y[i]; for(int i=1;i<=n;i++)y[i]=abs(y[i]); deque <int> stk; for(int i=1;i<=n;i++) { if(stk.size() && x[stk.back()]==x[i]) { if(y[i]>=y[stk.back()])continue; stk.pop_back(); } while(stk.size()>1 && equ(x[i],y[i],x[stk.back()],y[stk.back()])<equ(x[stk.back()],y[stk.back()],x[stk[stk.size()-2]],y[stk.size()-2])) stk.pop_back(); stk.push_back(i); } while(stk.size()>1 && equ(x[stk[0]],y[stk[0]],x[stk[1]],y[stk[1]])<0)stk.pop_front(); while(stk.size()>1 && equ(x[stk.back()],y[stk.back()],x[stk[stk.size()-2]],y[stk[stk.size()-2]])>l)stk.pop_front(); double mx=0.0; for(int i=0;i<stk.size();i++) { if(i) { double inter=equ(x[stk[i]],y[stk[i]],x[stk[i-1]],y[stk[i-1]]); mx=max(mx,dist(x[stk[i]],y[stk[i]],inter,0)); }else { mx=max(mx,dist(0,0,x[stk[0]],y[stk[0]])); } if(i<stk.size()-1) { double inter=equ(x[stk[i]],y[stk[i]],x[stk[i+1]],y[stk[i+1]]); mx=max(mx,dist(x[stk[i]],y[stk[i]],inter,0)); }else { mx=max(mx,dist(l,0,x[stk[i]],y[stk[i]])); } } 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...
#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...
#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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...