| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 407308 | phisti | Mobile (BOI12_mobile) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// https://oj.uz/problem/view/BOI12_mobile
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <queue>
#define sz(x) (int)size(x)
#define last_elem(coll) (*(coll.rbegin()))
#define FOR(x, e) for(u32 x = 0; x < (u32)(e); x++)
#define FORR(x, e) for(u32 x = (u32)(e) - 1; x < (u32)(e); x--)
#define FOB(x, b, e) for(auto x = (b); x != (e); x++)
#define FOI(x, e, i) for(u32 x = 0; x < (u32)e; x += (u32)(i))
#define FORE(x, C) for(auto& x: C)
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i16 = short;
using u16 = unsigned short;
using i8 = char;
using u8 = unsigned char;
using f64 = double;
using f32 = float;
using si = i32;
using sl = i64;
using ui = u32;
using ul = u64;
using vsl = std::vector<i64>;
using vsi = std::vector<i32>;
using vss = std::vector<i16>;
using vul = std::vector<u64>;
using vui = std::vector<u32>;
using vus = std::vector<u16>;
#ifdef MY_COMPILE
auto stin = std::ifstream("TestSamples/BIO12_Mobile-oj.in");
auto sout = std::ofstream("TestSamples/BIO12_Mobile-oj.out");
#elif OLDERN
auto stin = std::ifstream("bcount.in");
auto sout = std::ofstream("bcount.out");
#else
auto &stin = std::cin;
auto &sout = std::cout;
#endif
bool is_covered(
vector<pair<sl, sl>>& towers,
vector<pair<double, si>>& in_outs,
double power,
sl length)
{
ul idx = 0;
double p2 = power*power;
FORE(tower, towers) {
if (power > tower.second) {
auto val = sqrt(power * power - tower.second * tower.second);
in_outs[idx++] = make_pair(max(tower.first - val, 0.0), 1);
in_outs[idx++] = make_pair(min(tower.first + val, length * 1.0), -1);
}
}
sort(in_outs.begin(), in_outs.begin() + idx);
if (idx == 0 || in_outs[0].first > 0 || in_outs[idx - 1].first < length) { return false; }
si sum = 0;
sl i = 0;
while(in_outs[i].first == 0) {
sum+=in_outs[i++].second;
}
if (sum == 0) { return false; }
while(i < idx && in_outs[i].first < length) {
sum += in_outs[i].second;
if (sum == 0 && i < idx - 1 && in_outs[i + 1].first > in_outs[i].first) {
return false;
}
i++;
}
return true;
}
int main()
{
ul N, L;
stin >> N >> L;
vector<pair<sl, sl>> towers(N);
vector<pair<double, si>> patches(2*N);
FORE(p, towers) stin >> p.first >> p.second;
sl maxY = 0;
FORE(p, towers) maxY = max(maxY, abs(p.second));
double in = 0, ax = maxY + L;
while(ax - in > 0.0000001) {
auto ean = in + (ax - in) / 2;
if (is_covered(towers, patches, ean, L)) {
ax = ean;
} else {
in = ean;
}
}
sout << ax;
return 0;
}