Submission #1057606

#TimeUsernameProblemLanguageResultExecution timeMemory
1057606lucascgarMobile (BOI12_mobile)C++17
45 / 100
1097 ms24764 KiB
#include <bits/stdc++.h> // #pragma GCC optimize("Ofast,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; /* chutar resposta x: p toda torre achar achar menor e maior ponto com distância menor que x se intervalo tem algum ponto cego: x é válido se não, nn é achar pontos p torre: busca binária */ 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; } pii p[MAXN]; int l; long double right(int t, long double d){ long double sq = d*d; if (p[t].first > l) return l * (dist(p[t], {l,0}) <= sq); long double in=max(0, p[t].first), fi = l, me; if (dist({in,0}, p[t]) > sq) return -1; if (dist({l, 0}, p[t]) <= sq) return l; while (fi-in>=PRECISION){ me = (in+fi)/2.00; if (dist({me, 0}, p[t]) <= sq){ in = me; }else fi = me; } return in; } 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(5); 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; while (fi-in >= PRECISION){ me = (in+fi)/2.00; long double r=0; bool vl = 1; for (int i=0;i<n;i++){ if (dist(p[i], {r, 0}) <= me*me){ vl=0; r = right(i, me); } } vl = vl || (l!=r); if (vl) in=me; else fi=me; } cout << in << '\n'; return 0; }
#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...