QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#415329 | #7184. Transport Pluses | pandapythoner | WA | 0ms | 3936kb | C++20 | 3.6kb | 2024-05-20 18:55:36 | 2024-05-20 18:55:36 |
Judging History
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