QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#171388#7184. Transport Plusesucup-team1074#WA 1ms3784kbC++203.4kb2023-09-09 16:54:172023-09-09 16:55:47

Judging History

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

  • [2023-09-09 16:55:47]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3784kb
  • [2023-09-09 16:54:17]
  • 提交

answer

#include <bits/stdc++.h>

#define endl "\n"
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define pb push_back

struct Node {
    int number;
    int x;
    int y;
};

void solve () {
    int n, t, aid = 0;
    cin >> n >> t;
    pair<int, int> p[n + 5];
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    PII pst, ped;
    int dst = 1e9, ded = 1e9;
    int idst = -1, ided = -1;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].first >> p[i].second;
        if (dst > abs (p[i].first - x1)) {
            dst = abs (p[i].first - x1);
            pst = { p[i].first, y1 };
            idst = i;
        }
        if (dst > abs (p[i].second - y1)) {
            dst = abs (p[i].second - y1);
            pst = { x1, p[i].second };
            idst = i;
        }
        if (ded > abs (p[i].first - x2)) {
            ded = abs (p[i].first - x2);
            ped = { p[i].first, y2 };
            ided = i;
        }
        if (ded > abs (p[i].second - y2)) {
            ded = abs (p[i].second - y2);
            ped = { x2, p[i].second };
            ided = i;
        }
    }
    double ans = sqrt ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
    vector<Node> path[3];
    path[0].push_back ({ 0, x2, y2 });
    if (n == 0) {
        cout << ans << endl;
        cout << 1 << endl;
        cout << 0 << " " << x2 << " " << y2 << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        int tx = p[i].first, ty = p[i].second;
        vector<Node> tmp;
        int tans = 0;
        double cnt = 0;
        if (abs (x1 - tx) > abs (y1 - ty)) {
            tmp.push_back ({ 0, x1, ty });
        }
        else {
            tmp.push_back ({ 0, tx, y1 });
        }
        if (abs (x2 - tx) > abs (y2 - ty)) {
            tmp.push_back ({ i, x2, ty });
        }
        else {
            tmp.push_back ({ i, tx, y2 });
        }
        tmp.push_back ({ 0, x2, y2 });
        int lx = x1, ly = y1;
        for (auto [id, x, y] : tmp) {
            if (!id) {
                tans += sqrt ((x - lx) * (x - lx) + (y - ly) * (y - ly));
            }
            else {
                tans += t;
            }
            lx = x, ly = y;
        }
        if (tans < ans) {
            path[1] = tmp;
            aid = 1;
            ans = tans;
        }
    }
    if (ided != idst) {
        path[2].push_back ({ 0, pst.first, pst.second });
        path[2].push_back ({ idst, p[ided].first, p[ided].second });
        path[2].push_back ({ ided, ped.first, ped.second });
        path[2].push_back ({ 0, x2, y2 });
        int tans = 0, lx = x1, ly = y1;
        for (auto [id, x, y] : path[2]) {
            if (!id) {
                tans += sqrt ((x - lx) * (x - lx) + (y - ly) * (y - ly));
            }
            else {
                tans += t;
            }
            lx = x, ly = y;
        }
        if (tans < ans) {
            aid = 2;
            ans = tans;
        }
    }

    cout << setprecision (10) << fixed << ans << endl;
    cout << path[aid].size () << endl;
    for (auto [id, x, y] : path[aid]) {
        cout << id << " " << x << " " << y << endl;
    }
}

int main () {
    std::ios::sync_with_stdio (false);
    std::cin.tie (nullptr);
    std::cout.tie (nullptr);

    solve ();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 2
1 1
5 3
6 2

output:

4.0000000000
3
0 1 2
1 6 3
0 5 3

result:

ok correct

Test #2:

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

input:

2 1
1 1
6 1
1 3
6 3

output:

2.0000000000
4
0 1 1
1 6 3
2 6 1
0 6 1

result:

ok correct

Test #3:

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

input:

0 0
1 1
1 1

output:

0
1
0 1 1

result:

ok correct

Test #4:

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

input:

0 0
100 100
0 0

output:

141.421
1
0 0 0

result:

ok correct

Test #5:

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

input:

1 0
100 100
0 0
100 100

output:

100.0000000000
3
0 100 100
1 100 0
0 0 0

result:

ok correct

Test #6:

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

input:

1 0
100 100
0 0
100 0

output:

0.0000000000
3
0 100 100
1 0 0
0 0 0

result:

ok correct

Test #7:

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

input:

1 0
100 100
0 0
0 100

output:

0.0000000000
3
0 100 100
1 0 0
0 0 0

result:

ok correct

Test #8:

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

input:

1 100
50 50
0 0
50 50

output:

70.7106781187
1
0 0 0

result:

ok correct

Test #9:

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

input:

1 100
50 50
0 0
0 50

output:

70.7106781187
1
0 0 0

result:

ok correct

Test #10:

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

input:

1 100
50 50
0 0
51 51

output:

70.7106781187
1
0 0 0

result:

ok correct

Test #11:

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

input:

1 100
50 50
0 0
2 53

output:

70.7106781187
1
0 0 0

result:

ok correct

Test #12:

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

input:

1 100
0 0
100 100
50 50

output:

141.4213562373
1
0 100 100

result:

ok correct

Test #13:

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

input:

1 33
0 0
100 100
50 50

output:

133.0000000000
3
0 50 0
1 50 100
0 100 100

result:

ok correct

Test #14:

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

input:

1 12
100 0
11 90
0 100

output:

122.0000000000
3
0 0 0
1 11 100
0 11 90

result:

ok correct

Test #15:

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

input:

1 12
100 0
10 89
0 100

output:

122.0000000000
3
0 0 0
1 0 89
0 10 89

result:

ok correct

Test #16:

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

input:

2 1
2 1
5 1
1 3
6 3

output:

3.0000000000
1
0 5 1

result:

ok correct

Test #17:

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

input:

2 2
2 1
5 1
1 3
6 3

output:

3.0000000000
1
0 5 1

result:

ok correct

Test #18:

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

input:

1 2
1 1
5 3
7 2

output:

4.0000000000
3
0 1 2
1 5 2
0 5 3

result:

ok correct

Test #19:

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

input:

1 2
1 1
5 4
6 2

output:

4.0000000000
3
0 1 2
1 6 4
0 5 4

result:

ok correct

Test #20:

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

input:

12 1
77 80
76 78
77 81
76 79
77 78
75 80
75 79
76 80
78 81
77 81
76 81
76 80
77 79
76 79

output:

1.0000000000
3
0 77 80
3 76 78
0 76 78

result:

ok correct

Test #21:

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

input:

5 1
40 69
37 71
37 69
36 71
38 70
40 72
40 71

output:

1.0000000000
3
0 40 69
1 37 71
0 37 71

result:

ok correct

Test #22:

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

input:

8 1
84 27
86 32
85 31
83 27
86 27
85 28
83 27
83 32
85 31
87 29

output:

1.0000000000
3
0 84 27
3 86 32
0 86 32

result:

ok correct

Test #23:

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

input:

11 1
95 30
99 36
96 33
95 36
94 30
98 33
98 36
97 31
99 33
99 31
98 35
95 36
100 32

output:

1.0000000000
3
0 95 30
2 99 36
0 99 36

result:

ok correct

Test #24:

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

input:

4 1
19 37
18 32
18 36
21 36
19 33
22 34

output:

2.0000000000
3
0 18 37
1 18 32
0 18 32

result:

ok correct

Test #25:

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

input:

7 1
49 6
48 8
46 3
49 9
45 6
43 3
49 8
43 8
48 2

output:

1.0000000000
3
0 49 6
5 48 8
0 48 8

result:

ok correct

Test #26:

score: -100
Wrong Answer
time: 0ms
memory: 3588kb

input:

10 0
75 31
74 34
77 36
79 34
74 37
75 32
76 31
81 37
79 34
77 28
80 36
80 28

output:

0.0000000000
4
0 75 31
4 79 34
2 74 34
0 74 34

result:

wrong answer step 2: target (79.000000, 34.000000) not on plus (75.000000, 32.000000)