Submission #671708

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
671708	2022-12-13T15:25:31 Z	havingfun854	Mobile (BOI12_mobile)	C++11	100 / 100	739 ms	43804 KB

mobile

// https://oj.uz/problem/view/BOI12_mobile
#include <bits/stdc++.h>
using namespace std;

#define forint(i, from, toinc) for (int i = from; i <= toinc; ++i)
#define sq(x) (x)*(x)
#define all(x) x.begin(), x.end()

void fio()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef USEFILE
    freopen("mobile.in", "r", stdin);
    freopen("mobile.out", "w", stdout);
#endif
}

/*
    some observations:

    if we have 2 towers with the same x, (x, y1) and (x, y2),
    we only need to keep the one with the smallest abs y value,
    let's say |y1| <= |y2|, then we can safely forget (x, y2), because for any
    point on the x axis, it will always be closer (<=) to (x, y1) than to (x, y2).

    we do a simple binary search on distance d to see if all points between [0,L]
    can be covered by d.

    when trying to see if the segments covers the entire [0,len] range,
    we do NOT have to sort the segments, because if a later one (one corresponding
    to a tower with greater x value) connects with the current range
    while a earlier one does not, we know from geometry that the later one
    will extend further to the right as well, making not considering the earlier one
    inconsequential. but this time, don't break when seeing a gap.
 */

struct Point {
    int x,y;
};
struct Range {
    double from, to;
    bool operator<(const Range &o) const {
        return from == o.from ? to > o.to : from < o.from;
        // same from rank the one with the larger to first
    }
};

int tcnt;                   // tower count
vector<Point> towers;
int len;                    // all points on (0,0) to (len,0) to the towers
vector<Range> ranges;
int rcnt;

void debug()
{
    cerr << "highway from (0,0) to (" << len << ",0)" << endl;

    cerr << tcnt << " towers:";
    forint(i, 0, tcnt-1) {
        cerr << " " << towers[i].x << "," << towers[i].y;
    }
    cerr << endl;

    cerr << rcnt << " ranges:";
    forint(i, 0, rcnt-1) {
        cerr << " [" << ranges[i].from << "," << ranges[i].to << "]";
    }
    cerr << endl;
}

void rdata()
{
    cin >> tcnt >> len;

    int lastx, lasty;       // lasty >= 0
    cin >> lastx >> lasty;
    lasty = abs(lasty);

    forint(i, 1, tcnt-1) {
        int x, y;
        cin >> x >> y;
        if (x != lastx) {
            towers.push_back({lastx, lasty});
            lastx = x;
            lasty = abs(y);
        } else if (abs(y) < abs(lasty)) {
            lasty = abs(y);
        }
        if (i == tcnt-1) {
            towers.push_back({lastx, lasty});
        }
    }

    tcnt = (int)towers.size();
}


bool can_cover(double d)
{
    ranges.clear();

    forint(i, 0, tcnt-1) {
        double x = towers[i].x;
        double y = towers[i].y;
        if (d > y) {
            double dx = sqrt(sq(d) - sq(y));
            if (x-dx > len || x+dx < 0) continue;
            ranges.push_back({x-dx, x+dx});
        }
    }
    rcnt = (int)ranges.size();

    // sort(all(ranges));

#ifdef DEBUG
    debug();
#endif

    double right = 0;
    forint(i, 0, rcnt-1) {
        if (ranges[i].from <= right) {
            right = max(ranges[i].to, right);
            if (right >= len) break;
        }
    }

    bool res = right >= len;
#ifdef DEBUG
    cerr << "d=" << d << " can" << (res ? "" : "not") << " cover all" << endl;
#endif
    return res;
}

inline
double d2(int i, double x)  // tower i to (x,0)
{
    return sq(towers[i].x - x) + sq(towers[i].y);
}

int main()
{
    fio();
    rdata();
#ifdef DEBUG
    debug();
#endif

    double dends2 = d2(0, 0);
    dends2 = max(dends2, d2(0, len));
    dends2 = max(dends2, d2(tcnt-1, 0));
    dends2 = max(dends2, d2(tcnt-1, len));

    double dmax = sqrt(dends2);

    double d = dmax+1;
    for (double step = dmax; step > 1e-4; step /= 2) {
        while (d-step > 0 && can_cover(d-step)) {
            d -= step;
        }
    }
    cout << fixed << setprecision(3) << d << '\n';

    return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct

Subtask #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	468 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	2 ms	484 KB	Output is correct

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	4 ms	588 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	2 ms	596 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	4 ms	468 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	476 KB	Output is correct
2	Correct	4 ms	528 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	2 ms	596 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	2952 KB	Output is correct
2	Correct	43 ms	2188 KB	Output is correct
3	Correct	27 ms	2136 KB	Output is correct
4	Correct	22 ms	3292 KB	Output is correct
5	Correct	7 ms	596 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	468 KB	Output is correct
2	Correct	14 ms	2008 KB	Output is correct
3	Correct	19 ms	2616 KB	Output is correct
4	Correct	22 ms	3268 KB	Output is correct
5	Correct	26 ms	3440 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	3156 KB	Output is correct
2	Correct	40 ms	1832 KB	Output is correct
3	Correct	39 ms	2640 KB	Output is correct
4	Correct	31 ms	3532 KB	Output is correct
5	Correct	15 ms	1356 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	1780 KB	Output is correct
2	Correct	38 ms	2000 KB	Output is correct
3	Correct	20 ms	984 KB	Output is correct
4	Correct	32 ms	3460 KB	Output is correct
5	Correct	23 ms	3412 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	3288 KB	Output is correct
2	Correct	38 ms	1752 KB	Output is correct
3	Correct	21 ms	1064 KB	Output is correct
4	Correct	31 ms	3564 KB	Output is correct
5	Correct	25 ms	3344 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	386 ms	12532 KB	Output is correct
2	Correct	108 ms	668 KB	Output is correct
3	Correct	86 ms	764 KB	Output is correct
4	Correct	136 ms	12572 KB	Output is correct
5	Correct	119 ms	17992 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	760 KB	Output is correct
2	Correct	286 ms	12632 KB	Output is correct
3	Correct	99 ms	3456 KB	Output is correct
4	Correct	138 ms	12756 KB	Output is correct
5	Correct	124 ms	12460 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	474 ms	21548 KB	Output is correct
2	Correct	105 ms	600 KB	Output is correct
3	Correct	106 ms	9252 KB	Output is correct
4	Correct	183 ms	33492 KB	Output is correct
5	Correct	132 ms	19012 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	134 ms	580 KB	Output is correct
2	Correct	334 ms	21560 KB	Output is correct
3	Correct	102 ms	2588 KB	Output is correct
4	Correct	176 ms	21820 KB	Output is correct
5	Correct	145 ms	17072 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	558 ms	22320 KB	Output is correct
2	Correct	115 ms	576 KB	Output is correct
3	Correct	121 ms	10680 KB	Output is correct
4	Correct	203 ms	35888 KB	Output is correct
5	Correct	145 ms	17592 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	120 ms	540 KB	Output is correct
2	Correct	354 ms	22268 KB	Output is correct
3	Correct	148 ms	3492 KB	Output is correct
4	Correct	199 ms	22276 KB	Output is correct
5	Correct	167 ms	21552 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	551 ms	23128 KB	Output is correct
2	Correct	133 ms	460 KB	Output is correct
3	Correct	139 ms	12312 KB	Output is correct
4	Correct	249 ms	38736 KB	Output is correct
5	Correct	175 ms	23632 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	140 ms	520 KB	Output is correct
2	Correct	401 ms	22948 KB	Output is correct
3	Correct	145 ms	3428 KB	Output is correct
4	Correct	221 ms	23088 KB	Output is correct
5	Correct	186 ms	22028 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	739 ms	24716 KB	Output is correct
2	Correct	164 ms	496 KB	Output is correct
3	Correct	179 ms	15176 KB	Output is correct
4	Correct	302 ms	43804 KB	Output is correct
5	Correct	209 ms	25652 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	488 KB	Output is correct
2	Correct	463 ms	24488 KB	Output is correct
3	Correct	197 ms	4620 KB	Output is correct
4	Correct	271 ms	24644 KB	Output is correct
5	Correct	233 ms	23352 KB	Output is correct

Submission #671708

Compilation message