QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#675422 | #7184. Transport Pluses | aYi_7 | WA | 7ms | 7108kb | C++23 | 3.2kb | 2024-10-25 18:33:40 | 2024-10-25 18:33:41 |
Judging History
answer
#include <bits/stdc++.h>
// #define pii pair<int, int>
#define int long long
// using namespace std;
struct node {
double dis;
int x, y;
int prex, prey;
// bool tag; // 是否在线上
bool operator>(const node& a) const { return dis > a.dis; }
};
void solve() {
int n, t;
std::cin >> n >> t;
int xh, yh, xe, ye;
std::cin >> xh >> yh >> xe >> ye;
std::map<std::pair<int, int>, std::set<std::pair<int, int>>> eg;
std::map<std::pair<int, int>, std::pair<int, int>> rood;
std::map<std::pair<int, int>, double> dis;
std::set<int> x, y;
std::priority_queue<node, std::vector<node>, std::greater<node>> q;
for (int i = 0; i < n; i++) {
int a, b;
std::cin >> a >> b;
x.insert(a);
y.insert(b);
for (int j = 0; j <= 100; j++) {
for (int k = 0; k <= 100; k++) {
eg[{a, j}].emplace(k, b);
eg[{a, j}].emplace(a, k);
}
}
for (int j = 0; j <= 100; j++) {
for (int k = 0; k <= 100; k++) {
eg[{j, b}].emplace(k, b);
eg[{j, b}].emplace(a, k);
}
}
q.emplace(std::abs(a - xh), a, yh, xh, yh);
q.emplace(std::abs(b - yh), xh, b, xh, yh);
}
while (!q.empty()) {
auto now = q.top();
q.pop();
int di = now.dis;
std::pair<int, int> cur = std::make_pair(now.x, now.y);
if (dis.count(cur)) continue;
dis[cur] = di;
rood[cur] = std::make_pair(now.prex, now.prey);
for (auto& cur1 : eg[cur]) {
if (dis.count(cur1)) continue;
q.emplace(di + t, cur1.first, cur1.second, cur.first, cur.second);
}
}
double ans = std::sqrt((double)(xh - xe) * (double)(xh - xe) +
(double)(yh - ye) * (double)(yh - ye));
double len = 1e8;
for (auto& [cur, di] : dis) {
auto& [cx, cy] = cur;
if (cx != xe || cy != ye) continue;
double cost = std::max(std::fabs(cx - xe), std::fabs(cy - ye)) + di;
if (cost < len) {
len = cost;
if (cx != xe || cy != ye) rood[{xe, ye}] = cur;
}
}
auto check = [&](int X, int Y) -> bool {
return x.count(X) || y.count(Y);
};
if (ans < len) {
// std::cout << ans << '\n';
printf("%.10f\n", ans);
std::cout << 1 << '\n';
std::cout << 0 << ' ' << xe << ' ' << ye << '\n';
} else {
// std::cout << len << '\n';
printf("%.10f\n", len);
std::vector<std::pair<int, int>> ans_rood;
std::pair<int, int> cur = {xe, ye};
while (cur.first != xh || cur.second != yh) {
ans_rood.emplace_back(cur);
cur = rood[cur];
}
std::reverse(ans_rood.begin(), ans_rood.end());
std::cout << ans_rood.size() << '\n';
for(int i = 0; i < n; i++) {
}
}
}
signed main() {
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
int t = 1;
// std::cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 7ms
memory: 7108kb
input:
1 2 1 1 5 3 6 2
output:
4.4721359550 1 0 5 3
result:
wrong answer read 4.472136 but expected 4.000000, error = 0.472136