QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#183449#7184. Transport PlusesScarlett_boyWA 1ms6080kbC++173.5kb2023-09-19 15:27:212023-09-19 15:27:21

Judging History

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

  • [2023-09-19 15:27:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6080kb
  • [2023-09-19 15:27:21]
  • 提交

answer

#include "bits/stdc++.h"

typedef long long ll;
using namespace std;

const int N = 5e4 + 10, M = 5e5 + 10;

int n, t;
struct Point {
    int x, y;
} A, B, s[110];
vector<pair<int, int>> G[110][110];

double dis(Point X, Point Y) {
    return sqrt(1.0 * (X.x - Y.x) * (X.x - Y.x) + (X.y - Y.y) * (X.y - Y.y));
}


double Min_D[110][110][110];
vector<tuple<int, double, double>> vec;
double Ans = 1e9;

void solve() {
    cin >> n >> t;
    cin >> A.x >> A.y >> B.x >> B.y;
    for (int i = 1; i <= n; i++) {
        cin >> s[i].x >> s[i].y;
    }
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            for (int k = 1; k <= n; k++) {
                Min_D[k][i][j] = min(abs(s[k].x - i), abs(s[k].y - j));
            }
        }
    }
    // 不用 t
    if (Ans < dis(A, B)) {
        Ans = dis(A, B);
        vec = {{0, B.x, B.y}};
    }
    // 用一个 t
    for (int i = 1; i <= n; i++) {
        double D = Min_D[i][A.x][A.y] + t + Min_D[i][B.x][B.y];
        if (D < Ans) {
            Point now = A;
            Ans = D;
            vec.clear();
            if (now.x != s[i].x && now.y != s[i].y) {
                if (abs(now.x - s[i].x) < abs(now.y - s[i].y)) {
                    now.x = s[i].x;
                    vec.emplace_back(0, s[i].x, now.y);
                } else {
                    now.y = s[i].y;
                    vec.emplace_back(0, now.x, s[i].y);
                }
            }
            Point tmp = B;
            if (tmp.x != s[i].x && tmp.y != s[i].y) {
                if (abs(tmp.x - s[i].x) < abs(tmp.y - s[i].y)) {
                    tmp.x = s[i].x;
                } else {
                    tmp.y = s[i].y;
                }
                if (now.x != tmp.x || now.y != tmp.y) vec.emplace_back(i, tmp.x, tmp.y);
                vec.emplace_back(0, B.x, B.y);
            } else {
                if (now.x != tmp.x || now.y != tmp.y) vec.emplace_back(i, tmp.x, tmp.y);
            }
        }
    }
    // 用两个 t

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            double D = Min_D[i][A.x][A.y] + 2 * t + Min_D[j][B.x][B.y];
            if (D < Ans) {
                Ans = D;
                vec.clear();
                Point now = A;
                if (abs(now.x - s[i].x) < abs(now.y - s[i].y)) {
                    now.x = s[i].x;
                    vec.emplace_back(0, s[i].x, now.y);
                } else {
                    now.y = s[i].y;
                    vec.emplace_back(0, now.x, s[i].y);
                }

                vec.emplace_back(i, s[i].x, s[j].y);

                Point tmp = B;
                if (abs(tmp.x - s[j].x) < abs(tmp.y - s[j].y)) {
                    tmp.x = s[j].x;
                } else {
                    tmp.y = s[j].y;
                }
                vec.emplace_back(j, tmp.x, tmp.y);
                vec.emplace_back(0, B.x, B.y);
            }
        }
    }

    cout << fixed << setprecision(12) << Ans << '\n';
    cout << vec.size() << '\n';
    for (auto [id, a, b]: vec) {
        cout << id << " ";
        cout << fixed << setprecision(12) << a << " " << b << '\n';
    }
}


signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int _ = 1;
//    cin >> _;
    for (int o = 1; o <= _; o++) {
        solve();
    }
    return 0;
}
/*


33333 99999
133331
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 2
1 1
5 3
6 2

output:

4.000000000000
3
0 1.000000000000 2.000000000000
1 5.000000000000 2.000000000000
0 5.000000000000 3.000000000000

result:

ok correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 6080kb

input:

2 1
1 1
6 1
1 3
6 3

output:

2.000000000000
4
0 1.000000000000 1.000000000000
1 1.000000000000 3.000000000000
2 6.000000000000 1.000000000000
0 6.000000000000 1.000000000000

result:

ok correct

Test #3:

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

input:

0 0
1 1
1 1

output:

1000000000.000000000000
0

result:

wrong answer claimed 1000000000.0000000000, actual 0.0000000000