Submission #1163531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163531		kedimestan	Mobile (BOI12_mobile)	C++20	0 / 100	845 ms	16068 KiB

mobile

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

// Function to calculate the Euclidean distance from a point (x, 0) on the highway to a BTS at (xi, yi)
double distance(double x, double xi, double yi) {
    return sqrt((x - xi) * (x - xi) + yi * yi);
}

// Function to find the nearest BTS to a point (x, 0) on the highway
double nearestDistance(double x, const vector<pair<double, double>>& stations) {
    double minDist = 1e18; // Initialize with a large value
    for (const auto& station : stations) {
        double dist = distance(x, station.first, station.second);
        if (dist < minDist) {
            minDist = dist;
        }
    }
    return minDist;
}

int main() {
    int N, L;
    cin >> N >> L;

    vector<pair<double, double>> stations(N);
    for (int i = 0; i < N; ++i) {
        cin >> stations[i].first >> stations[i].second;
    }

    // Binary search to find the point x[q] that maximizes the distance to the nearest BTS
    double left = 0.0, right = L;
    double maxDist = 0.0;

    // Perform binary search until the search space is small enough
    while (right - left > 1e-7) {
        double mid = (left + right) / 2.0;

        // Find the nearest distance at mid and mid + epsilon
        double distMid = nearestDistance(mid, stations);
        double distMidEpsilon = nearestDistance(mid + 1e-7, stations);

        // Update the maximum distance found so far
        if (distMid > maxDist) {
            maxDist = distMid;
        }

        // Adjust the search boundaries based on whether we are on the increasing or decreasing part
        if (distMid < distMidEpsilon) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Output the result with the required precision
    cout << fixed << setprecision(6) << maxDist << endl;

    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