oj.uz

답안 #671333

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
671333 2022-12-12T21:04:55 Z havingfun854 Mobile (BOI12_mobile) C++11
0 / 100
 189 ms 16852 KB 
// 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.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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