Submission #96211

#TimeUsernameProblemLanguageResultExecution timeMemory
96211easruiMobile (BOI12_mobile)C++14
8 / 100
1077 ms47360 KiB
#include <bits/stdc++.h> using namespace std; const int MN = 1e6+5; int N,L,C[MN],num[MN],cur,pos; double X[MN],Y[MN],A[MN],B[MN],Ipos[MN],x,ans=0,tmp; bool cmp(int a, int b) { if(B[a]==B[b]) return A[a]<A[b]; return B[a]<B[b]; } double getI(int a, int b) { return (B[a]-B[b])/(A[b]-A[a]); } int main() { //freopen("C:\\Users\\user\\Desktop\\input.txt","r",stdin); cin >> N >> L; for(int i=0; i<N; i++){ cin >> X[i] >> Y[i]; A[i] = -2*X[i]; B[i] = X[i]*X[i]+Y[i]*Y[i]; num[i] = i; } sort(num,num+N,cmp); Ipos[pos] = 0; C[pos] = num[0]; for(int i=1; i<N; i++){ cur = num[i]; //cout << cur << '\n'; while(1){ x = getI(C[pos],cur); if(x<=0 || x>=L) break; if(x>Ipos[pos]){ Ipos[++pos] = x; C[pos] = cur; break; } pos--; } } Ipos[pos+1] = L; for(int i=0; i<=pos; i++){ cur = C[i]; //cout << X[cur] << '\n'; tmp = max((Ipos[i]-X[cur])*(Ipos[i]-X[cur]),(Ipos[i+1]-X[cur])*(Ipos[i+1]-X[cur]))+Y[cur]*Y[cur]; /*if(X[cur]<Ipos[i]) tmp = (Ipos[i]-X[cur])*(Ipos[i]-X[cur])+Y[cur]*Y[cur]; else if(X[cur]>Ipos[i]) tmp = (Ipos[i+1]-X[cur])*(Ipos[i+1]-X[cur])+Y[cur]*Y[cur]; else tmp = B[cur];*/ ans = max(ans,tmp); } cout << sqrt(ans); }
#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...