QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#216849 | #7184. Transport Pluses | cardinal_city# | WA | 0ms | 4000kb | C++23 | 2.7kb | 2023-10-16 02:22:03 | 2023-10-16 02:22:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define smx(a, b) a = max(a, b);
#define smn(a, b) a = min(a, b);
#define pb push_back
#define endl '\n'
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;
mt19937 rng(time(0));
int t;
double xh, yh;
struct Mov {
int typ; double x, y;
};
struct Path {
double nrg = 0.0;
vector<Mov> movs;
bool operator< (const Path &o) const {
return nrg < o.nrg;
}
void calc() {
double cx = xh, cy = yh;
for (auto &mv : movs) {
if (mv.typ > 0) nrg += t;
else nrg += hypot(mv.x - cx, mv.y - cy);
cx = mv.x; cy = mv.y;
}
}
void print() {
cout << nrg << '\n';
cout << movs.size() << '\n';
for (auto &mv : movs) {
cout << mv.typ << ' ' << mv.x << ' ' << mv.y << '\n';
}
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
cout << setprecision(12);
int n; cin >> n >> t;
cin >> xh >> yh;
double xe, ye; cin >> xe >> ye;
vector<Path> paths;
// straight line
Path straight;
straight.movs.pb({0, 1.0*xe, 1.0*ye});
straight.calc();
paths.pb(straight);
vector<array<double, 2>> pluses(n);
rep(i, 0, n) {
cin >> pluses[i][0] >> pluses[i][1];
}
// one plus
auto toplus = [&](double x, double y, int pi) -> array<double, 2> {
double d1 = abs(pluses[pi][0] - x);
double d2 = abs(pluses[pi][1] - y);
if (d1 < d2) return {pluses[pi][0], y};
return {x, pluses[pi][1]};
};
for (int i = 0; i < n; i++) {
Path p;
auto to = toplus(xh, yh, i);
auto from = toplus(xe, ye, i);
p.movs.pb({0, to[0], to[1]});
p.movs.pb({i+1, from[0], from[1]});
p.movs.pb({0, xe, ye});
p.calc();
paths.pb(p);
}
// two plus
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Path p;
auto to = toplus(xh, yh, i);
auto from = toplus(xe, ye, j);
array<double, 2> inter = {pluses[i][0], pluses[j][1]};
p.movs.pb({0, to[0], to[1]});
p.movs.pb({i+1, inter[0], inter[1]});
p.movs.pb({j+1, from[0], from[1]});
p.movs.pb({0, from[0], from[1]});
p.calc();
paths.pb(p);
//p.print();
}
}
sort(all(paths));
paths[0].print();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
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: 0ms
memory: 4000kb
input:
2 1 1 1 6 1 1 3 6 3
output:
2 4 0 1 1 1 1 3 1 6 3 0 6 3
result:
wrong answer arrived at (6.000000, 3.000000) instead of (6.000000, 1.000000)