QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#216849#7184. Transport Plusescardinal_city#WA 0ms4000kbC++232.7kb2023-10-16 02:22:032023-10-16 02:22:03

Judging History

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

  • [2023-10-16 02:22:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4000kb
  • [2023-10-16 02:22:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define smx(a, b) a = max(a, b);
#define smn(a, b) a = min(a, b);
#define pb push_back
#define endl '\n'

const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;

mt19937 rng(time(0));

int t;
double xh, yh;

struct Mov {
    int typ; double x, y;
};

struct Path {
    double nrg = 0.0;
    vector<Mov> movs;

    bool operator< (const Path &o) const {
        return nrg < o.nrg;
    }

    void calc() {
        double cx = xh, cy = yh;
        for (auto &mv : movs) {
            if (mv.typ > 0) nrg += t;
            else nrg += hypot(mv.x - cx, mv.y - cy);
            cx = mv.x; cy = mv.y;
        }
    }

    void print() {
        cout << nrg << '\n';
        cout << movs.size() << '\n';
        for (auto &mv : movs) {
            cout << mv.typ << ' ' << mv.x << ' ' << mv.y << '\n';
        }
    }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
    cout << setprecision(12);
    int n; cin >> n >> t;
    cin >> xh >> yh;
    double xe, ye; cin >> xe >> ye;

    vector<Path> paths;
    // straight line
    Path straight;
    straight.movs.pb({0, 1.0*xe, 1.0*ye});
    straight.calc();
    paths.pb(straight);

    vector<array<double, 2>> pluses(n);
    rep(i, 0, n) {
        cin >> pluses[i][0] >> pluses[i][1];
    }

    // one plus
    auto toplus = [&](double x, double y, int pi) -> array<double, 2> {
        double d1 = abs(pluses[pi][0] - x);
        double d2 = abs(pluses[pi][1] - y);
        if (d1 < d2) return {pluses[pi][0], y};
        return {x, pluses[pi][1]};
    };
    for (int i = 0; i < n; i++) {
        Path p;
        auto to = toplus(xh, yh, i);
        auto from = toplus(xe, ye, i);
        p.movs.pb({0, to[0], to[1]});
        p.movs.pb({i+1, from[0], from[1]});
        p.movs.pb({0, xe, ye});
        p.calc();
        paths.pb(p);
    }

    // two plus
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            Path p;
            auto to = toplus(xh, yh, i);
            auto from = toplus(xe, ye, j);
            array<double, 2> inter = {pluses[i][0], pluses[j][1]};
            p.movs.pb({0, to[0], to[1]});
            p.movs.pb({i+1, inter[0], inter[1]});
            p.movs.pb({j+1, from[0], from[1]});
            p.movs.pb({0, from[0], from[1]});
            p.calc();
            paths.pb(p);
            //p.print();
        }
    }

    sort(all(paths));
    paths[0].print();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
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: 0ms
memory: 4000kb

input:

2 1
1 1
6 1
1 3
6 3

output:

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

result:

wrong answer arrived at (6.000000, 3.000000) instead of (6.000000, 1.000000)