답안 #671368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671368	2022-12-13T01:37:17 Z	havingfun854	Mobile (BOI12_mobile)	C++11	75 / 100	1000 ms	24764 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.
 */

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;
        } else {
            break;
        }
    }

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

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

    double dends2 = sq(towers[0].x + len) + sq(towers[0].y);
    dends2 = max(dends2, sq(1.0 * towers[tcnt-1].x) + sq(towers[tcnt-1].y));
    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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	4 ms	340 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	5 ms	340 KB	Output is correct

Subtask #4
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	11 ms	500 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct

Subtask #5
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	11 ms	468 KB	Output is correct
3	Correct	2 ms	212 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	468 KB	Output is correct
2	Correct	11 ms	504 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	2392 KB	Output is correct
2	Correct	168 ms	1924 KB	Output is correct
3	Correct	140 ms	1880 KB	Output is correct
4	Correct	26 ms	2384 KB	Output is correct
5	Correct	8 ms	340 KB	Output is correct

Subtask #8
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	468 KB	Output is correct
2	Correct	22 ms	1364 KB	Output is correct
3	Correct	29 ms	2324 KB	Output is correct
4	Correct	29 ms	2384 KB	Output is correct
5	Correct	34 ms	2456 KB	Output is correct

Subtask #9
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	173 ms	3156 KB	Output is correct
2	Correct	154 ms	1796 KB	Output is correct
3	Correct	388 ms	2384 KB	Output is correct
4	Correct	40 ms	2632 KB	Output is correct
5	Correct	17 ms	848 KB	Output is correct

Subtask #10
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	123 ms	1744 KB	Output is correct
2	Correct	127 ms	1724 KB	Output is correct
3	Correct	66 ms	764 KB	Output is correct
4	Correct	38 ms	2556 KB	Output is correct
5	Correct	31 ms	2448 KB	Output is correct

Subtask #11
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	137 ms	3280 KB	Output is correct
2	Correct	128 ms	1752 KB	Output is correct
3	Correct	60 ms	784 KB	Output is correct
4	Correct	39 ms	2552 KB	Output is correct
5	Correct	32 ms	2512 KB	Output is correct

Subtask #12
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	837 ms	12672 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #13
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	105 ms	712 KB	Output is correct
2	Correct	508 ms	12472 KB	Output is correct
3	Correct	507 ms	3156 KB	Output is correct
4	Correct	185 ms	12512 KB	Output is correct
5	Correct	165 ms	12224 KB	Output is correct

Subtask #14
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1012 ms	21488 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #15
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	113 ms	588 KB	Output is correct
2	Correct	581 ms	21492 KB	Output is correct
3	Correct	412 ms	2320 KB	Output is correct
4	Correct	227 ms	17232 KB	Output is correct
5	Correct	191 ms	16772 KB	Output is correct

Subtask #16
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1090 ms	22320 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #17
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	131 ms	544 KB	Output is correct
2	Correct	671 ms	22200 KB	Output is correct
3	Correct	774 ms	3384 KB	Output is correct
4	Correct	260 ms	18096 KB	Output is correct
5	Correct	230 ms	17328 KB	Output is correct

Subtask #18
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1092 ms	23056 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #19
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	146 ms	460 KB	Output is correct
2	Correct	757 ms	22956 KB	Output is correct
3	Correct	743 ms	3404 KB	Output is correct
4	Correct	287 ms	18896 KB	Output is correct
5	Correct	250 ms	17836 KB	Output is correct

Subtask #20
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1072 ms	24696 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #21
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	171 ms	460 KB	Output is correct
2	Correct	877 ms	24552 KB	Output is correct
3	Correct	950 ms	4508 KB	Output is correct
4	Correct	376 ms	24764 KB	Output is correct
5	Correct	328 ms	23496 KB	Output is correct

답안 #671368

Compilation message