QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415327#7184. Transport PlusespandapythonerWA 0ms3936kbC++203.6kb2024-05-20 18:55:082024-05-20 18:55:10

Judging History

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

  • [2024-05-20 18:55:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3936kb
  • [2024-05-20 18:55:08]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;
mt19937 rnd(234);

int n;
flt d;
pair<flt, flt> s, t;
vector<pair<flt, flt>> a;
flt eps = 1e-9;


flt dist(const pair<flt, flt>& a, const pair<flt, flt>& b) {
    flt dx = a.first - b.first;
    flt dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}


flt dist_to_pulse(const pair<flt, flt>& a, const pair<flt, flt>& b) {
    return min(abs(a.first - b.first), abs(a.second - b.second));
}


int go_by_plus_count(const pair<flt, flt>& a, const pair<flt, flt>& b, const pair<flt, flt>& p, int i) {
    ll cnt = 0;
    if (min(abs(a.first - p.first), abs(a.second - p.second)) > eps) {
        cnt += 1;
    }
    if (min(abs(b.first - p.first), abs(b.second - p.second)) > eps) {
        cnt += 2;
    } else {
        cnt += 1;
    }
    return cnt;
}


void go_by_plus(const pair<flt, flt>& a, const pair<flt, flt>& b, const pair<flt, flt>& p, int i) {
    if (min(abs(a.first - p.first), abs(a.second - p.second)) > eps) {
        if (abs(a.first - p.first) < abs(a.second - p.second)) {
            cout << 0 << " " << p.first << " " << a.second << "\n";
        } else {
            cout << 0 << " " << a.first << " " << p.second << "\n";
        }
    }
    if (min(abs(b.first - p.first), abs(b.second - p.second)) > eps) {
        if (abs(b.first - p.first) < abs(b.second - p.second)) {
            cout << i + 1 << " " << p.first << " " << b.second << "\n";
        } else {
            cout << i + 1 << " " << b.first << " " << p.second << "\n";
        }
        cout << 0 << " " << b.first << " " << b.second << "\n";
    } else {
        cout << i + 1 << " " << b.first << " " << b.second << "\n";
    }
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> d;
    cin >> s.first >> s.second;
    cin >> t.first >> t.second;
    a.resize(n);
    for (int i = 0; i < n; i += 1) {
        cin >> a[i].first >> a[i].second;
    }
    flt rs = dist(s, t);
    for (int i = 0; i < n; i += 1) {
        rs = min(rs, dist_to_pulse(s, a[i]) + d + dist_to_pulse(t, a[i]));
    }
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < n; j += 1) {
            if (i == j) {
                continue;
            }
            rs = min(rs, dist_to_pulse(s, a[i]) + 2 * d + dist_to_pulse(t, a[j]));
        }
    }
    cout << fixed << setprecision(10) << rs << "\n";
    if (abs(rs - dist(s, t)) < eps) {
        cout << 1 << "\n";
        cout << t.first << " " << t.second << "\n";
        return 0;
    }
    for (int i = 0; i < n; i += 1) {
        if (abs(rs - (dist_to_pulse(s, a[i]) + d + dist_to_pulse(t, a[i]))) < eps) {
            int cnt = go_by_plus_count(s, t, a[i], i);
            cout << cnt << "\n";
            go_by_plus(s, t, a[i], i);
            return 0;
        }
    }
    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < n; j += 1) {
            if (i == j) {
                continue;
            }
            if (abs(rs - dist_to_pulse(s, a[i]) + 2 * d + dist_to_pulse(t, a[j]))) {
                pair<flt, flt> mid = { a[i].first, a[j].second };
                int cnt = go_by_plus_count(s, mid, a[i], i) + go_by_plus_count(mid, t, a[j], j);
                cout << cnt << "\n";
                go_by_plus(s, mid, a[i], i);
                go_by_plus(mid, t, a[j], j);
                return 0;
            }
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3864kb

input:

1 2
1 1
5 3
6 2

output:

4.0000000000
3
0 1.0000000000 2.0000000000
1 5.0000000000 2.0000000000
0 5.0000000000 3.0000000000

result:

ok correct

Test #2:

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

input:

2 1
1 1
6 1
1 3
6 3

output:

2.0000000000
2
1 1.0000000000 3.0000000000
2 6.0000000000 1.0000000000

result:

ok correct

Test #3:

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

input:

0 0
1 1
1 1

output:

0.0000000000
1
1.0000000000 1.0000000000

result:

wrong output format Expected integer, but "1.0000000000" found