QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164854#7184. Transport Plusesucup-team1448#WA 1ms3992kbC++141.8kb2023-09-05 14:10:272023-09-05 14:10:27

Judging History

你现在查看的是最新测评结果

  • [2023-09-05 14:10:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3992kb
  • [2023-09-05 14:10:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
template <typename T> void rd(T &x) {
    x = 0;
    int f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - 48;
        c = getchar();
    }
    x *= f;
}
template <typename T, typename... T2> void rd(T &x, T2 &...y) {
    rd(x), rd(y...);
}

using db = double;
const int Nmax = 105;
int n, t;
struct Point {
    int x, y;
} h, e, p[Nmax];
int dis(Point a, Point b) { return min(abs(a.x - b.x), abs(a.y - b.y)); }
bool f(Point a, Point b) { return abs(a.x - b.x) > abs(a.y - b.y); }
#define out(a, b) f(a, b) ? a.x : b.x, f(a, b) ? b.y : a.y
db ans;
int p1, p2;
int main() {
    rd(n, t, h.x, h.y, e.x, e.y);
    if (n) {
        for (int i = 1; i <= n; ++i) {
            rd(p[i].x, p[i].y);
        }
        for (int i = 1; i <= n; ++i) {
            if (!p1 || dis(h, p[p1]) > dis(h, p[i])) p1 = i;
            if (!p2 || dis(e, p[p2]) > dis(e, p[i])) p2 = i;
        }
        ans = dis(h, p[p1]) + dis(e, p[p2]) + t * 2;
        if (ans > hypot(e.x - h.x, e.y - h.y)) {
            ans = hypot(e.x - h.x, e.y - h.y);
            p1 = p2 = 0;
        }
        for (int i = 1; i <= n; ++i) {
            if (ans > dis(h, p[i]) + dis(e, p[i]) + t) {
                ans = dis(h, p[i]) + dis(e, p[i]) + t;
                p1 = i;
                p2 = 0;
            }
        }
    }
    printf("%.9lf\n", ans);
    if (!p1 && !p2) {
        printf("1\n0 %d %d", e.x, e.y);
    } else if (!p2) {
        printf("3\n0 %d %d\n%d %d %d\n0 %d %d", out(h, p[p1]), p1,
               out(e, p[p1]), e.x, e.y);
    } else {
        printf("4\n0 %d %d\n%d %d %d\n%d %d %d\n0 %d %d", out(h, p[p1]), p1,
               p[p1].x, p[p2].y, p2, out(e, p[p2]), e.x, e.y);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3992kb

input:

1 2
1 1
5 3
6 2

output:

4.000000000
3
0 1 2
1 6 3
0 5 3

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 3976kb

input:

2 1
1 1
6 1
1 3
6 3

output:

2.000000000
4
0 1 1
1 1 3
2 6 1
0 6 1

result:

ok correct

Test #3:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

0 0
1 1
1 1

output:

0.000000000
1
0 1 1

result:

ok correct

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3852kb

input:

0 0
100 100
0 0

output:

0.000000000
1
0 0 0

result:

wrong answer claimed 0.0000000000, actual 141.4213562373