QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164882#7184. Transport Plusesucup-team1055#WA 1ms3936kbC++173.1kb2023-09-05 14:23:202023-09-05 14:23:21

Judging History

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

  • [2023-09-05 14:23:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3936kb
  • [2023-09-05 14:23:20]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = int(s); i < int(n); i++)
#define rrep(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template <class T> bool chmin(T &a, T b) {
    if (a <= b) return false;
    a = b;
    return true;
}

template <class T> bool chmax(T &a, T b) {
    if (a >= b) return false;
    a = b;
    return true;
}

int main() {
    int n, t;
    std::cin >> n >> t;
    int xh, yh, xe, ye;
    std::cin >> xh >> yh >> xe >> ye;
    auto cost = [&](int x1, int y1, int x2, int y2) -> ld {
        return std::sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    };
    ld ans = cost(xh, yh, xe, ye);
    std::vector<std::tuple<int, int, int>> pxy;
    pxy.emplace_back(0, xe, ye);
    std::vector<std::pair<int, int>> ps(n);
    for (auto &[x, y] : ps) {
        std::cin >> x >> y;
    }
    // plusを1つだけ使う
    rep(i, 0, n) {
        auto [x, y] = ps[i];
        ld ret = 0;
        std::vector<std::tuple<int, int, int>> a;
        if (x != xh && y != yh) {
            if (std::abs(x - xh) < std::abs(y - yh)) {
                a.emplace_back(0, x, yh);
                ret += std::abs(x - xh);
            } else {
                a.emplace_back(0, xh, y);
                ret += std::abs(y - yh);
            }
        }
        ret += t;
        if (std::abs(xe - x) < std::abs(ye - y)) {
            a.emplace_back(i + 1, x, ye);
            ret += std::abs(xe - x);
            a.emplace_back(0, xe, ye);
        } else {
            a.emplace_back(i + 1, xe, y);
            ret += std::abs(ye - y);
            a.emplace_back(0, xe, ye);
        }
        if (chmin(ans, ret)) {
            pxy = a;
        }
    }
    rep(i, 0, n) {
        rep(j, 0, n) {
            if (i == j) continue;
            auto [xi, yi] = ps[i];
            auto [xj, yj] = ps[j];
            ld ret = 0;
            std::vector<std::tuple<int, int, int>> a;
            if (xi != xh && yi != yh) {
                if (std::abs(xi - xh) < std::abs(yi - yh)) {
                    a.emplace_back(0, xi, yh);
                    ret += std::abs(xi - xh);
                } else {
                    a.emplace_back(0, xh, yi);
                    ret += std::abs(yi - yh);
                }
            }
            ret += t;
            a.emplace_back(1, xi, yj);
            ret += t;
            if (std::abs(xe - xj) < std::abs(ye - yj)) {
                a.emplace_back(i + 1, xj, ye);
                ret += std::abs(xe - xj);
                a.emplace_back(0, xe, ye);
            } else {
                a.emplace_back(i + 1, xe, yj);
                ret += std::abs(ye - yj);
                a.emplace_back(0, xe, ye);
            }
            if(chmin(ans, ret)) {
                pxy = a;
            }
        }
    }
    std::cout << std::setprecision(15);
    std::cout << ans << '\n';
    std::cout << pxy.size() << '\n';
    for(auto [p, x, y]: pxy) {
        std::cout << p << " " << x << " " << y << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 2
1 1
5 3
6 2

output:

4
3
0 1 2
1 5 2
0 5 3

result:

ok correct

Test #2:

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

input:

2 1
1 1
6 1
1 3
6 3

output:

2
3
1 1 3
1 6 1
0 6 1

result:

wrong answer step 2: target (6.000000, 1.000000) not on plus (1.000000, 3.000000)