QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#675150 | #7184. Transport Pluses | liaoyd | WA | 0ms | 4020kb | C++23 | 5.7kb | 2024-10-25 18:02:28 | 2024-10-25 18:02:29 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define double long double
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef const double* (*p_fun)(const double*, int);
const LL N = 3e3 + 10, M = 2e3 + 10, mod = 1e9 + 7, LLF = 1e15,
null = 0x3f3f3f3f3f3f3f;
template <typename T>
bool chmax(T& a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T, typename... Args>
bool chmax(T& a, const T& b, const Args&... args) {
bool updated = chmax(a, b);
return chmax(a, args...) || updated;
}
template <typename T>
bool chmin(T& a, const T& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <typename T, typename... Args>
bool chmin(T& a, const T& b, const Args&... args) {
bool updated = chmin(a, b);
return chmin(a, args...) || updated;
}
class UnionFind {
public:
vector<int> parent;
vector<int> size;
int n;
// 当前连通分量数目
int setCount;
public:
UnionFind(int _n) : n(_n), setCount(_n), parent(_n), size(_n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
--setCount;
return true;
}
bool connected(int x, int y) {
x = find(x);
y = find(y);
return x == y;
}
};
int qmi(int a, int b) {
int res = 1;
a %= mod;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int sqrt(int x) {
int l = 0, r = 3e9; // LLONG_MAX
while (l < r) {
int mid = (l + r + 1) >> 1;
if (mid * mid > x)
r = mid - 1; // 向下取整
else
l = mid;
}
return r;
}
struct node {
int op;
double x, y;
};
double dis(double& bgx, double& bgy, double& edx, double& edy) {
return sqrt(pow(bgx - edx, 2) + pow(bgy - edy, 2));
}
static inline void solve() {
int n;
double t;
cin >> n >> t;
double bgx, bgy, edx, edy;
cin >> bgx >> bgy >> edx >> edy;
vector<pii> v(n + 1);
for (int i = 1; i <= n; i++)
cin >> v[i].x >> v[i].y;
vector<vector<node>> ans(4);
double s1 = dis(bgx, bgy, edx, edy);
ans[1].push_back({ 0,edx,edy });
node t1 = {}, t2 = {};
int posj = 0, posy = 0, mnj = LLF, mny = LLF, mn2 = LLF;
double x2 = LLF;
int jl = 0;
for (int i = 1; i <= n; i++) {
double disx = abs(v[i].x - bgx), disy = abs(v[i].y - bgy);
double s2 = min(disx, disy);
double disxf = abs(v[i].x - edx), disyf = abs(v[i].y - edy);
double s2f = min(disxf, disyf);
x2 = min(x2, s2 + s2f + t);
if (x2 == s2 + s2f + t) {
jl = i;
}
}
int z1, y1;
double an1 = LLF, an2 = LLF;
for (int i = 1; i <= n; i++) {
double disx = abs(v[i].x - bgx), disy = abs(v[i].y - bgy);
double s2 = min(disx, disy);
double disxf = abs(v[i].x - edx), disyf = abs(v[i].y - edy);
double s2f = min(disxf, disyf);
an1 = min(an1, s2);
an2 = min(an2, s2f);
if (an1 == s2) { z1 = i; }
if (an2 == s2f) { y1 = i; }
}
double ans3 = min(abs(v[z1].x - bgx) , abs(v[z1].y - bgy)) + min(abs(v[y1].x - edx) , abs(v[y1].y - edy)) + 2 * t;
double aan = min({ ans3,s1,x2 });
//cout << aan << "\n";
cout << fixed << setprecision(5) << aan << endl;
if (aan == s1) {
cout << ans[1].size() << "\n";
for (auto e : ans[1]) {
cout << e.op << " " << e.first << " " << e.second << "\n";
}
}
else if (aan == x2) {
if (abs(v[jl].x - bgx) <= abs(v[jl].y - bgy)) {
node ta = { 0,v[jl].x,bgy };
ans[2].push_back(ta);
}
else {
node ta = { 0,bgx,v[jl].y };
ans[2].push_back(ta);
}
if (abs(v[jl].x - edx) <= abs(v[jl].y - edy)) {
node ta = { jl,v[jl].x,edy };
ans[2].push_back(ta);
}
else {
node ta = { jl,edx,v[jl].y };
ans[2].push_back(ta);
}
node ta = { 0,edx,edy };
ans[2].push_back(ta);
cout << ans[2].size() << "\n";
for (auto e : ans[2]) {
cout << e.op << " " << e.first << " " << e.second << "\n";
}
}
else {
if (abs(v[z1].x - bgx) <= abs(v[z1].y - bgy)) {
node ta = { 0,v[z1].x,bgy };
ans[3].push_back(ta);
}
else {
node ta = { 0,bgx,v[z1].y };
ans[3].push_back(ta);
}
node ta = { z1, v[z1].x,v[y1].y };
ans[3].push_back({ ta });
if (abs(v[y1].x - edx) <= abs(v[y1].y - edy)) {
node ta = { y1,edx,v[y1].y };
ans[3].push_back(ta);
}
else {
node ta = { y1,v[y1].x,v[y1].y };
ans[3].push_back(ta);
}
ta = { 0,edx,edy };
ans[3].push_back(ta);
cout << ans[3].size() << "\n";
for (auto e : ans[3]) {
cout << e.op << " " << e.first << " " << e.second << "\n";
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << unitbuf;
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3884kb
input:
1 2 1 1 5 3 6 2
output:
4.00000 3 0 1.00000 2.00000 1 6.00000 3.00000 0 5.00000 3.00000
result:
ok correct
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 4020kb
input:
2 1 1 1 6 1 1 3 6 3
output:
2.00000 4 0 1.00000 1.00000 1 1.00000 3.00000 2 6.00000 3.00000 0 6.00000 1.00000
result:
wrong answer claimed 2.0000000000, actual 4.0000000000