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 <iostream>
#include <bits/stdc++.h>
#include <array>
#include <fstream>
#include <string>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
using ll=long long;
double N, L;
vector<pair<double, double>> c; //{x, y}
bool check(double R){ //checks to see if max distance >=R is possible; find last true
vector<pair<double, double>> I;
for (pair<double, double> coord: c){
double x=coord.first, y=coord.second;
I.push_back({x-sqrt(R*R-y*y), x+sqrt(R*R-y*y)});
}
sort(I.begin(), I.end());
// for (auto p: I) cout<<"("<<p.first<<" "<<p.second<<") ";
// cout<<"\n";
int s=0;
double M=-1000000000; //M=max endpoint so far
while (I[s].first<0) M=max(M, I[s].second), s++;
for (int i=s; i<N; i++){ //since I.size()==N
if (I[i].first>M) return true;
M=max(M, I[i].second);
}
if (L>M) return true;
return false;
}
int main() {
cin>>N>>L;
for (int i=0; i<N; i++){
double x, y;
cin>>x>>y;
c.push_back({x, y});
}
ll lo=0, hi=1000000000000000;
lo--;
while (lo < hi) {
ll mid = lo + (hi - lo + 1) / 2;
double R=mid/1000000.0;
if (check(R)) {
lo = mid;
} else {
hi = mid - 1;
}
}
cout<<setprecision(6)<<lo/1000000.0;
// cout<<check(5);
}
# | 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... |
# | 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... |
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |