QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183449 | #7184. Transport Pluses | Scarlett_boy | WA | 1ms | 6080kb | C++17 | 3.5kb | 2023-09-19 15:27:21 | 2023-09-19 15:27:21 |
Judging History
answer
#include "bits/stdc++.h"
typedef long long ll;
using namespace std;
const int N = 5e4 + 10, M = 5e5 + 10;
int n, t;
struct Point {
int x, y;
} A, B, s[110];
vector<pair<int, int>> G[110][110];
double dis(Point X, Point Y) {
return sqrt(1.0 * (X.x - Y.x) * (X.x - Y.x) + (X.y - Y.y) * (X.y - Y.y));
}
double Min_D[110][110][110];
vector<tuple<int, double, double>> vec;
double Ans = 1e9;
void solve() {
cin >> n >> t;
cin >> A.x >> A.y >> B.x >> B.y;
for (int i = 1; i <= n; i++) {
cin >> s[i].x >> s[i].y;
}
for (int i = 0; i <= 100; i++) {
for (int j = 0; j <= 100; j++) {
for (int k = 1; k <= n; k++) {
Min_D[k][i][j] = min(abs(s[k].x - i), abs(s[k].y - j));
}
}
}
// 不用 t
if (Ans < dis(A, B)) {
Ans = dis(A, B);
vec = {{0, B.x, B.y}};
}
// 用一个 t
for (int i = 1; i <= n; i++) {
double D = Min_D[i][A.x][A.y] + t + Min_D[i][B.x][B.y];
if (D < Ans) {
Point now = A;
Ans = D;
vec.clear();
if (now.x != s[i].x && now.y != s[i].y) {
if (abs(now.x - s[i].x) < abs(now.y - s[i].y)) {
now.x = s[i].x;
vec.emplace_back(0, s[i].x, now.y);
} else {
now.y = s[i].y;
vec.emplace_back(0, now.x, s[i].y);
}
}
Point tmp = B;
if (tmp.x != s[i].x && tmp.y != s[i].y) {
if (abs(tmp.x - s[i].x) < abs(tmp.y - s[i].y)) {
tmp.x = s[i].x;
} else {
tmp.y = s[i].y;
}
if (now.x != tmp.x || now.y != tmp.y) vec.emplace_back(i, tmp.x, tmp.y);
vec.emplace_back(0, B.x, B.y);
} else {
if (now.x != tmp.x || now.y != tmp.y) vec.emplace_back(i, tmp.x, tmp.y);
}
}
}
// 用两个 t
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
double D = Min_D[i][A.x][A.y] + 2 * t + Min_D[j][B.x][B.y];
if (D < Ans) {
Ans = D;
vec.clear();
Point now = A;
if (abs(now.x - s[i].x) < abs(now.y - s[i].y)) {
now.x = s[i].x;
vec.emplace_back(0, s[i].x, now.y);
} else {
now.y = s[i].y;
vec.emplace_back(0, now.x, s[i].y);
}
vec.emplace_back(i, s[i].x, s[j].y);
Point tmp = B;
if (abs(tmp.x - s[j].x) < abs(tmp.y - s[j].y)) {
tmp.x = s[j].x;
} else {
tmp.y = s[j].y;
}
vec.emplace_back(j, tmp.x, tmp.y);
vec.emplace_back(0, B.x, B.y);
}
}
}
cout << fixed << setprecision(12) << Ans << '\n';
cout << vec.size() << '\n';
for (auto [id, a, b]: vec) {
cout << id << " ";
cout << fixed << setprecision(12) << a << " " << b << '\n';
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int _ = 1;
// cin >> _;
for (int o = 1; o <= _; o++) {
solve();
}
return 0;
}
/*
33333 99999
133331
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4120kb
input:
1 2 1 1 5 3 6 2
output:
4.000000000000 3 0 1.000000000000 2.000000000000 1 5.000000000000 2.000000000000 0 5.000000000000 3.000000000000
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 6080kb
input:
2 1 1 1 6 1 1 3 6 3
output:
2.000000000000 4 0 1.000000000000 1.000000000000 1 1.000000000000 3.000000000000 2 6.000000000000 1.000000000000 0 6.000000000000 1.000000000000
result:
ok correct
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3984kb
input:
0 0 1 1 1 1
output:
1000000000.000000000000 0
result:
wrong answer claimed 1000000000.0000000000, actual 0.0000000000