# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
96213 |
2019-02-07T05:43:56 Z |
easrui |
Mobile (BOI12_mobile) |
C++14 |
|
814 ms |
86448 KB |
#include <bits/stdc++.h>
using namespace std;
const int MN = 1e6+5;
int N,L,C[MN],num[MN],cur,pos;
long double X[MN],Y[MN],A[MN],B[MN],Ipos[MN],x,ans=0,tmp;
bool cmp(int a, int b)
{
if(A[a]==A[b]) return B[a]<B[b];
return A[a]>A[b];
}
double getI(int a, int b)
{
if(A[a]==A[b]) return L;
return (B[a]-B[b])/(A[b]-A[a]);
}
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
//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){
if(pos==-1){
Ipos[++pos] = 0;
C[pos] = cur;
break;
}
x = getI(C[pos],cur);
if(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 time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
568 KB |
Output is correct |
2 |
Correct |
3 ms |
632 KB |
Output is correct |
3 |
Correct |
3 ms |
504 KB |
Output is correct |
4 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
760 KB |
Output is correct |
2 |
Incorrect |
7 ms |
760 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
764 KB |
Output is correct |
2 |
Incorrect |
5 ms |
732 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
760 KB |
Output is correct |
2 |
Incorrect |
5 ms |
760 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
5368 KB |
Output is correct |
2 |
Incorrect |
56 ms |
5432 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
5580 KB |
Output is correct |
2 |
Correct |
62 ms |
5240 KB |
Output is correct |
3 |
Incorrect |
58 ms |
5880 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
7988 KB |
Output is correct |
2 |
Incorrect |
61 ms |
5980 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
74 ms |
7096 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
96 ms |
7564 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
317 ms |
43540 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
382 ms |
33608 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
387 ms |
52088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
478 ms |
40420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
482 ms |
60648 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
538 ms |
47032 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
508 ms |
69300 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
614 ms |
53752 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
638 ms |
86448 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
814 ms |
67896 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |