Submission #827896

#	Time	Username	Problem	Language	Result	Execution time	Memory
827896		EntityPlantt	Mobile (BOI12_mobile)	C++17	0 / 100	1093 ms	131072 KiB

mobile

#define ONLINE_JUDGE
#include <cstdio>
#include <cmath>
#include <vector>
/*#include <windows.h>
const HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
inline void scta(const int &clr) { SetConsoleTextAttribute(handle, clr); }*/
using namespace std;
vector <pair <int, int>> points;
vector <pair <double, double>> intervals;
double radius;
int n, len, x, y, i;
double l, r = 2e9, m;
int main() {
    if (fopen("mobile.inp", "r")) {
        freopen("mobile.inp", "r", stdin);
        freopen("mobile.out", "w", stdout);
    }
    scanf("%d%d%d%d", &n, &len, &x, &y);
    points.push_back({x, abs(y)});
    while (--n) {
        scanf("%d%d", &x, &y);
        /*if (points.back().first == x) {
            if (y < 0) {
                points.back().second = -y;
            }
        }
        else*/ points.push_back({x, y});
    }
    while (r - l > 1e-8) {
        m = (l + r) / 2.0;
        intervals.clear();
        intervals.push_back({0.0, len});
        /*scta(7);
        printf("l = %lf, r = %lf, m = %lf\n", l, r, m);*/
        for (auto &point : points) {
            x = point.first;
            radius = sqrt(m * m - double(point.second) * double(point.second));
            /*scta(15);
            printf("  Intervals =");
            scta(14);
            for (auto &in : intervals) {
                printf(" (%lf, %lf)", in.first, in.second);
            }
            scta(15);
            printf("\n  place = %d, radius = %lf\n", x, radius);*/
            for (i = intervals.size() - 1; i >= 0; i--) {
                if (x - radius <= intervals[i].first && intervals[i].second <= x + radius) {
                    // scta(10); printf("    Entire interval is contained\n");
                    intervals.erase(intervals.begin() + i);
                }
                else if (x + radius <= intervals[i].first || intervals[i].second <= x - radius) {
                    // scta(12); printf("    None of the interval is contained\n");
                }
                else if (x - radius <= intervals[i].first && x + radius <= intervals[i].second) {
                    // scta(9); printf("    The left part of the interval is contained\n");
                    intervals[i].first = x + radius;
                }
                else if (intervals[i].first <= x - radius && intervals[i].second <= x + radius) {
                    // scta(13); printf("    The right part of the interval is contained\n");
                    intervals[i].second = x - radius;
                }
                else {
                    // scta(11); printf("    The interval has to be split into two\n");
                    intervals.push_back({x + radius, intervals[i].second});
                    intervals[i].second = x - radius;
                }
            }
            if (intervals.empty()) break;
        }
        if (intervals.empty()) r = m; else l = m;
    }
    printf("%lf\n", l);
    return 0;
}

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen("mobile.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen("mobile.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d%d%d%d", &n, &len, &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~

• 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