Submission #60975553

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Building {
    long long x, h;
};
// ビルが見えるかどうかを判定
bool canSeeAllBuildings(const vector<Building>& buildings, double height) {
    double maxSlope = -1e18;  // 現時点での最大傾き
    for (const auto& building : buildings) {
        double slope = (building.h - height) / building.x;
        if (slope <= maxSlope) {
            return false;  // 現在のビルが他のビルに遮られる
        }
        maxSlope = max(maxSlope, slope);
    }
    return true;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Building {
    long long x, h;
};

// ビルが見えるかどうかを判定
bool canSeeAllBuildings(const vector<Building>& buildings, double height) {
    double maxSlope = -1e18;  // 現時点での最大傾き
    for (const auto& building : buildings) {
        double slope = (building.h - height) / building.x;
        if (slope <= maxSlope) {
            return false;  // 現在のビルが他のビルに遮られる
        }
        maxSlope = max(maxSlope, slope);
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<Building> buildings(n);
    for (int i = 0; i < n; ++i) {
        cin >> buildings[i].x >> buildings[i].h;
    }

    // 高さを二分探索
    double low = 0.0, high = 1e9, result = -1.0;
    const double eps = 1e-9;

    while (high - low > eps) {
        double mid = (low + high) / 2.0;
        if (canSeeAllBuildings(buildings, mid)) {
            high = mid;  // 高さを下げられる
            result = mid;
        } else {
            low = mid;   // 高さを上げる必要がある
        }
    }

    if (canSeeAllBuildings(buildings, 0.0)) {
        cout << -1 << endl;  // 高さ 0 で全てのビルが見える場合
    } else {
        cout << fixed << setprecision(18) << result << endl;
    }

    return 0;
}

Submission Info

Judge Result