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 <bits/stdc++.h>
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
/*
chutar resposta x:
na ordem dada se torre pega ponto r, atualizar r pro maior ponto com distância menor que x
(ordem é sempre ótima pq se um cara à direita é melhor que um à esquerda p atingir r, então ele é melhor pra ir p direita tb)
se nn chguei até l, deu errado
se não, nn é
achar pontos p torre: busca binária
pitágoras p nn dar TLE:
p[i].second^2 + ex^2 = x^2
ex^2 = x^2 - p[i].second^2
ex = sqrt(x^2 - p[i].second^2)
*/
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int MAXN = 1e6+10;
const double PRECISION = 1e-5;
long double dist(pdd a, pdd b){
long double x = abs(a.first-b.first), y = abs(a.second-b.second);
return x*x + y*y;
}
pll p[MAXN];
int l;
signed main(){
std::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
cout << fixed << setprecision(6);
int n;
cin >> n >> l;
for (int i=0;i<n;i++){
cin >> p[i].first >> p[i].second;
}
long double in=0, fi = 2e9, me;
for (int q=0;q<100;q++){
me = (in+fi)/2.00;
long double sq = me*me;
long double r=0;
bool vl = 1;
for (int i=0;i<n;i++){
if (dist(p[i], {r, 0}) <= sq){
vl=0;
if (dist(p[i], {l, 0}) <= sq) r=l;
else{
// pitagoras
long double ex = sqrtl(sq - (p[i].second*p[i].second));
if (p[i].first+ex > r) r = p[i].first+ex;
}
}
if (r==l) break;
}
vl = vl || (l!=r);
if (vl) in=me;
else fi=me;
}
cout << in << '\n';
return 0;
}
# | 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... |