제출 #671333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671333		havingfun854	Mobile (BOI12_mobile)	C++11	0 / 100	189 ms	16852 KiB

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)

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).

    now we kind of cut the x axis into segments, enclosed by distinct x values we see.

    for points between (x1,0) and (x2,0), corresponding to two towers (x1,y1) and (x2,y2),
    the points equidistant to the two towers (x=,0) is the one with the max
    min distant to these two points, because moving left, we have a point
    that is closer to (x1,y1), and therefore a smaller max distance, and same for
    moving right.

    this point could still be closer to some other towers out of the [x1,x2] segment,
    but we don't need to worry about it, because this distance would still be greater
    than the one produced by the next segment.

    for two towers at (x1,y1) and (x2,y2), the equidistant point (x,0) to
    these towers has a close form of
        x = (x2+x1)/2 + (y2^2 - y1^2) / 2(x2-x1)

    if x2 < x, then the min distance is
        sqrt((x2-x1)^2 + y1^2)
    else if x > x1, min distance is
        sqrt((x2-x1)^2 + y2^2)
 */

struct Point {
    int x,y;
};

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

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;
}

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

    int lastx, lasty;
    cin >> lastx >> lasty;

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

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

double calc_maxd(int i1, int i2)
{
    double x1 = towers[i1].x;
    double y1 = towers[i1].y;
    double x2 = towers[i2].x;
    double y2 = towers[i2].y;
    double y12 = y1*y1;
    double y22 = y2*y2;
    double dx2 = (x2-x1)*(x2-x1);

    double x = (x2+x1) + (y22 - y12) / (x2-x1);
    x /= 2;

    double d2;  // d*d
    if (x < x1) {
        d2 = dx2 + y22;
    } else if (x > x2) {
        d2 = dx2 + y12;
    } else {
        d2 = y22 + (x2-x)*(x2-x);
    }
    
    return sqrt(d2);
}

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

    double minmaxd = DBL_MAX;
    forint(i, 0, tcnt-2) {
        minmaxd = min(minmaxd, calc_maxd(i, i+1));
    }
    cout << fixed << setprecision(3) << minmaxd << '\n';

    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