QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415329#7184. Transport PlusespandapythonerWA 0ms3936kbC++203.6kb2024-05-20 18:55:362024-05-20 18:55:36

Judging History

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

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

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 << 0 << " " << 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: 3936kb

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: 3828kb

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: 0
Accepted
time: 0ms
memory: 3920kb

input:

0 0
1 1
1 1

output:

0.0000000000
1
0 1.0000000000 1.0000000000

result:

ok correct

Test #4:

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

input:

0 0
100 100
0 0

output:

141.4213562373
1
0 0.0000000000 0.0000000000

result:

ok correct

Test #5:

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

input:

1 0
100 100
0 0
100 100

output:

100.0000000000
2
1 0.0000000000 100.0000000000
0 0.0000000000 0.0000000000

result:

ok correct

Test #6:

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

input:

1 0
100 100
0 0
100 0

output:

0.0000000000
1
1 0.0000000000 0.0000000000

result:

ok correct

Test #7:

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

input:

1 0
100 100
0 0
0 100

output:

0.0000000000
1
1 0.0000000000 0.0000000000

result:

ok correct

Test #8:

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

input:

1 100
50 50
0 0
50 50

output:

70.7106781187
1
0 0.0000000000 0.0000000000

result:

ok correct

Test #9:

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

input:

1 100
50 50
0 0
0 50

output:

70.7106781187
1
0 0.0000000000 0.0000000000

result:

ok correct

Test #10:

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

input:

1 100
50 50
0 0
51 51

output:

70.7106781187
1
0 0.0000000000 0.0000000000

result:

ok correct

Test #11:

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

input:

1 100
50 50
0 0
2 53

output:

70.7106781187
1
0 0.0000000000 0.0000000000

result:

ok correct

Test #12:

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

input:

1 100
0 0
100 100
50 50

output:

141.4213562373
1
0 100.0000000000 100.0000000000

result:

ok correct

Test #13:

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

input:

1 33
0 0
100 100
50 50

output:

133.0000000000
3
0 0.0000000000 50.0000000000
1 100.0000000000 50.0000000000
0 100.0000000000 100.0000000000

result:

ok correct

Test #14:

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

input:

1 12
100 0
11 90
0 100

output:

122.0000000000
3
0 100.0000000000 100.0000000000
1 11.0000000000 100.0000000000
0 11.0000000000 90.0000000000

result:

ok correct

Test #15:

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

input:

1 12
100 0
10 89
0 100

output:

122.0000000000
3
0 100.0000000000 100.0000000000
1 0.0000000000 89.0000000000
0 10.0000000000 89.0000000000

result:

ok correct

Test #16:

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

input:

2 1
2 1
5 1
1 3
6 3

output:

3.0000000000
1
0 5.0000000000 1.0000000000

result:

ok correct

Test #17:

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

input:

2 2
2 1
5 1
1 3
6 3

output:

3.0000000000
1
0 5.0000000000 1.0000000000

result:

ok correct

Test #18:

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

input:

1 2
1 1
5 3
7 2

output:

4.0000000000
3
0 1.0000000000 2.0000000000
1 5.0000000000 2.0000000000
0 5.0000000000 3.0000000000

result:

ok correct

Test #19:

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

input:

1 2
1 1
5 4
6 2

output:

4.0000000000
3
0 1.0000000000 2.0000000000
1 6.0000000000 4.0000000000
0 5.0000000000 4.0000000000

result:

ok correct

Test #20:

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

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
1
3 76.0000000000 78.0000000000

result:

ok correct

Test #21:

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

input:

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

output:

1.0000000000
1
1 37.0000000000 71.0000000000

result:

ok correct

Test #22:

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

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
1
3 86.0000000000 32.0000000000

result:

ok correct

Test #23:

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

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
1
2 99.0000000000 36.0000000000

result:

ok correct

Test #24:

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

input:

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

output:

2.0000000000
2
0 19.0000000000 36.0000000000
1 18.0000000000 32.0000000000

result:

ok correct

Test #25:

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

input:

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

output:

1.0000000000
1
5 48.0000000000 8.0000000000

result:

ok correct

Test #26:

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

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
3
0 77.0000000000 31.0000000000
1 77.0000000000 34.0000000000
2 74.0000000000 34.0000000000

result:

wrong answer claimed 0.0000000000, actual 2.0000000000