QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164788#7184. Transport Plusesucup-team1448#WA 1ms3952kbC++141.7kb2023-09-05 13:40:102023-09-05 13:40:10

Judging History

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

  • [2023-09-05 13:40:10]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3952kb
  • [2023-09-05 13:40:10]
  • 提交

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;
} s, 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, s.x, s.y, e.x, e.y);
    for (int i = 1; i <= n; ++i) {
        rd(p[i].x, p[i].y);
    }
    for (int i = 1; i <= n; ++i) {
        if (dis(s, p[i]) < dis(s, p[p1])) p1 = i;
        if (dis(e, p[i]) < dis(e, p[p2])) p2 = i;
    }
    ans = dis(s, p[p1]) + dis(e, p[p2]) + t * 2;
    if (ans > hypot(e.x - s.x, e.y - s.y)) {
        ans = hypot(e.x - s.x, e.y - s.y);
        p1 = p2 = 0;
    }
    for (int i = 1; i <= n; ++i) {
        if (ans > dis(s, p[i]) + dis(e, p[i]) + t) {
            ans = dis(s, 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(s, 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(s, p[p1]), p1,
               p[p1].x, p[p2].y, p2, out(e, p[2]), e.x, e.y);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3948kb

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: 3896kb

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: 3924kb

input:

0 0
100 100
0 0

output:

100.000000000
1
0 0 0

result:

wrong answer claimed 100.0000000000, actual 141.4213562373