QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#164830 | #7184. Transport Pluses | ucup-team087# | WA | 1ms | 3724kb | C++14 | 3.0kb | 2023-09-05 13:56:58 | 2023-09-05 13:56:58 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
constexpr double INF = 1e+12;
double sq(double r) { return r * r; }
int N;
Int T;
vector<Int> X, Y;
int main() {
for (; ~scanf("%d%lld", &N, &T); ) {
X.resize(N + 2);
Y.resize(N + 2);
for (int i = 0; i < N + 2; ++i) {
scanf("%lld%lld", &X[i], &Y[i]);
}
Int dist[2][110] = {};
pair<Int, Int> nearest[2][110] = {};
for (int i = 0; i < 2; ++i) for (int j = 2; j < N + 2; ++j) {
dist[i][j] = INF;
if (chmin(dist[i][j], abs(X[j] - X[i]))) nearest[i][j] = make_pair(X[j], Y[i]);
if (chmin(dist[i][j], abs(Y[j] - Y[i]))) nearest[i][j] = make_pair(X[i], Y[j]);
}
double ans = INF;
vector<pair<int, pair<Int, Int>>> ops;
// 0
{
if (chmin(ans, sq(X[1] - X[0]) + sq(Y[1] - Y[0]))) {
ops.clear();
ops.emplace_back(-1, make_pair(X[1], Y[1]));
}
}
// 1
for (int i = 2; i < N + 2; ++i) {
if (chmin<double>(ans, dist[0][i] + T + dist[1][i])) {
ops.clear();
ops.emplace_back(-1, nearest[0][i]);
ops.emplace_back(i, nearest[1][i]);
ops.emplace_back(-1, make_pair(X[1], Y[1]));
}
}
// 2
for (int i = 2; i < N + 2; ++i) for (int j = 2; j < N + 2; ++j) {
if (chmin<double>(ans, dist[0][i] + T + T + dist[1][j])) {
ops.clear();
ops.emplace_back(-1, nearest[0][i]);
ops.emplace_back(i, make_pair(X[j], Y[i]));
ops.emplace_back(j, nearest[1][j]);
ops.emplace_back(-1, make_pair(X[1], Y[1]));
}
}
printf("%.12f\n", ans);
printf("%d\n", (int)ops.size());
for (const auto &op : ops) {
printf("%d %lld %lld\n", max(op.first - 1, 0), op.second.first, op.second.second);
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3700kb
input:
1 2 1 1 5 3 6 2
output:
4.000000000000 3 0 1 2 1 6 3 0 5 3
result:
ok correct
Test #2:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
2 1 1 1 6 1 1 3 6 3
output:
2.000000000000 4 0 1 1 1 6 3 2 6 1 0 6 1
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
0 0 1 1 1 1
output:
0.000000000000 1 0 1 1
result:
ok correct
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3692kb
input:
0 0 100 100 0 0
output:
20000.000000000000 1 0 0 0
result:
wrong answer claimed 20000.0000000000, actual 141.4213562373