QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#164882 | #7184. Transport Pluses | ucup-team1055# | WA | 1ms | 3936kb | C++17 | 3.1kb | 2023-09-05 14:23:20 | 2023-09-05 14:23:21 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, s, n) for (int i = int(s); i < int(n); i++)
#define rrep(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <class T> bool chmin(T &a, T b) {
if (a <= b) return false;
a = b;
return true;
}
template <class T> bool chmax(T &a, T b) {
if (a >= b) return false;
a = b;
return true;
}
int main() {
int n, t;
std::cin >> n >> t;
int xh, yh, xe, ye;
std::cin >> xh >> yh >> xe >> ye;
auto cost = [&](int x1, int y1, int x2, int y2) -> ld {
return std::sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
};
ld ans = cost(xh, yh, xe, ye);
std::vector<std::tuple<int, int, int>> pxy;
pxy.emplace_back(0, xe, ye);
std::vector<std::pair<int, int>> ps(n);
for (auto &[x, y] : ps) {
std::cin >> x >> y;
}
// plusを1つだけ使う
rep(i, 0, n) {
auto [x, y] = ps[i];
ld ret = 0;
std::vector<std::tuple<int, int, int>> a;
if (x != xh && y != yh) {
if (std::abs(x - xh) < std::abs(y - yh)) {
a.emplace_back(0, x, yh);
ret += std::abs(x - xh);
} else {
a.emplace_back(0, xh, y);
ret += std::abs(y - yh);
}
}
ret += t;
if (std::abs(xe - x) < std::abs(ye - y)) {
a.emplace_back(i + 1, x, ye);
ret += std::abs(xe - x);
a.emplace_back(0, xe, ye);
} else {
a.emplace_back(i + 1, xe, y);
ret += std::abs(ye - y);
a.emplace_back(0, xe, ye);
}
if (chmin(ans, ret)) {
pxy = a;
}
}
rep(i, 0, n) {
rep(j, 0, n) {
if (i == j) continue;
auto [xi, yi] = ps[i];
auto [xj, yj] = ps[j];
ld ret = 0;
std::vector<std::tuple<int, int, int>> a;
if (xi != xh && yi != yh) {
if (std::abs(xi - xh) < std::abs(yi - yh)) {
a.emplace_back(0, xi, yh);
ret += std::abs(xi - xh);
} else {
a.emplace_back(0, xh, yi);
ret += std::abs(yi - yh);
}
}
ret += t;
a.emplace_back(1, xi, yj);
ret += t;
if (std::abs(xe - xj) < std::abs(ye - yj)) {
a.emplace_back(i + 1, xj, ye);
ret += std::abs(xe - xj);
a.emplace_back(0, xe, ye);
} else {
a.emplace_back(i + 1, xe, yj);
ret += std::abs(ye - yj);
a.emplace_back(0, xe, ye);
}
if(chmin(ans, ret)) {
pxy = a;
}
}
}
std::cout << std::setprecision(15);
std::cout << ans << '\n';
std::cout << pxy.size() << '\n';
for(auto [p, x, y]: pxy) {
std::cout << p << " " << x << " " << y << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3936kb
input:
1 2 1 1 5 3 6 2
output:
4 3 0 1 2 1 5 2 0 5 3
result:
ok correct
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3800kb
input:
2 1 1 1 6 1 1 3 6 3
output:
2 3 1 1 3 1 6 1 0 6 1
result:
wrong answer step 2: target (6.000000, 1.000000) not on plus (1.000000, 3.000000)