제출 #903921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
903921		tz74	Mobile (BOI12_mobile)	C++17	8 / 100	839 ms	18868 KiB

mobile

#include <iostream>
#include <vector>
#include <iomanip>
#include <ctgmath>

using namespace std;

using i64 = long long;
using f64 = double;

i64 N;
f64 L;
vector<pair<i64, i64> > towers;

f64 sq(f64 in) {
    return in * in;
}

bool contiguous(f64 R) {
    f64 rightmost = 0;

    for (int i = 0; i < N; i++) {
        f64 x = towers[i].first;
        f64 y = towers[i].second;
        f64 d = sq(2.0 * x) - 4.0 * (sq(x) + sq(y) - sq(R));

        if (d > 0) {
            f64 x1 = (2.0 * x - sqrt(d)) / 2;
            f64 x2 = (2.0 * x + sqrt(d)) / 2;

            // printf("i: %d, x1: %lf, x2: %lf\n", i, x1, x2);

            if (x1 < rightmost) {
                rightmost = max(rightmost, x2);
            }
        }
    }

    // printf("leftmost: %lf, rightmost: %lf\n", leftmost, rightmost);
    return rightmost >= L;
}

int main(void) {
    cin >> N >> L;
    for (int i = 0; i < N; i++) {
        pair<i64, i64> p;
        cin >> p.first >> p.second;
        towers.push_back(p);
    }

    // printf("contiguous: %d\n", contiguous(7.8102));
    // return 0;

    f64 lo = 1.0;
    f64 hi = 1.5e9;

    while (hi - lo > 1e-4) {
        f64 mid = (hi + lo) / 2;

        // we want the largest value where it's not contiguous
        if (contiguous(mid)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }

    cout << lo << endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 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