Submission #407328

#	Time	Username	Problem	Language	Result	Execution time	Memory
407328		phisti	Mobile (BOI12_mobile)	C++17	0 / 100	955 ms	16068 KiB

mobile

// https://oj.uz/problem/view/BOI12_mobile
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <queue>
#include <math.h>

#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,
    double power,
    sl length)
{
    auto p2 = power * power;
    double last = 0;
    FORE(t, towers) {
        if (p2 < t.second) continue;
        auto dist = sqrt(p2 - t.second);
        if (t.first - dist < last) last = t.first  + dist;
    }
    
    return last >= length;
}

int main()
{
    ul N, L;
    stin >> N >> L;
    
    vector<pair<sl, sl>> towers(N);
    
    FORE(p, towers) stin >> p.first >> p.second;
    
    sl maxY = 0;
    FORE(p, towers) {
        maxY = max(maxY, abs(p.second));
        p.second = p.second * p.second;
    }
    
    double in = 0, ax = maxY + L;
    while(ax - in > 0.0000001) {
        auto ean = in + (ax - in) / 2;
        if (is_covered(towers, ean, L)) {
            ax = ean;
        } else {
            in = ean;
        }
    }
    
    sout.precision(5);
    sout << fixed << ax;

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5