QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#608731 | #6124. King Of Zombies | qtoq | WA | 0ms | 3844kb | C++23 | 5.0kb | 2024-10-04 01:49:48 | 2024-10-04 01:49:50 |
Judging History
answer
//thatsramen
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)
using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;
//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;
//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';}
void dbg_out() {cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); }
template<typename T> bool mins(T& x, T y) { if (x > y) { x = y; return true; } return false; }
template<typename T> bool maxs(T& x, T y) { if (x < y) { x = y; return true; } return false; }
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//order_of_key(k): number of elements strictly less than k
//find_by_order(k): k-th element in the set
void setPrec() {cout << fixed << setprecision(15);}
void unsyncIO() {cin.tie(0)->sync_with_stdio(0);}
void setIn(string s) {freopen(s.c_str(), "r", stdin);}
void setOut(string s) {freopen(s.c_str(), "w", stdout);}
void setIO(string s = "") {
unsyncIO(); setPrec();
if(s.size()) setIn(s + ".in"), setOut(s + ".out");
}
// #define TEST_CASES
struct human {
pi cord, vel;
};
void solve() {
int n, d;
cin >> n >> d;
vector<human> al(n+1);
for (int i = 0; i <= n; i++) {
cin >> al[i].cord.ft >> al[i].cord.sd;
cin >> al[i].vel.ft >> al[i].vel.sd;
}
auto get = [&](int i, int j) -> ld {
auto [x1, y1] = al[i].cord;
auto [vx1, vy1] = al[i].vel;
auto [x2, y2] = al[j].cord;
auto [vx2, vy2] = al[j].vel;
// if (1ll * (x2-x1) * (vy1-vy2) == 1ll * (y2-y1)*(vx1-vx2)) {
// if ((x2-x1 >= 0 && vx1-vx2 >= 0) || (x2-x1 >= 0 && vx1-vx2 >= 0)) {
// }
// }
ld A = (vx1 - vx2)*(vx1 - vx2) + (vy1 - vy2)*(vy1 - vy2);
ld B = 2 * ((x1 - x2) * (vx1 - vx2) + (y1 - y2) * (vy1 - vy2));
ld C = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) - d*d;
if (C <= 0) {
return 0;
}
// Дискриминант
ld discriminant = B * B - 4 * A * C;
if (discriminant < 0) {
// Нет реального решения, нет касания
return INF; // Возвращаем отрицательное значение как индикатор отсутствия касания
}
// Вычисляем два возможных момента времени касания
ld t1 = (-B + sqrt(discriminant)) / (2 * A);
ld t2 = (-B - sqrt(discriminant)) / (2 * A);
// Нам нужно положительное время
if (t1 >= 0 && t2 >= 0) {
return min(t1, t2);
} else if (t1 >= 0) {
return t1;
} else if (t2 >= 0) {
return t2;
} else {
return INF; // Касания не произойдет
}
return INF;
};
for (int i = 0; i <= n; i++) {
auto [tx, ty] = al[i].cord;
auto [vx, vy] = al[i].vel;
// dbg(i, tx + 3 * vx, ty + 3 * vy);
}
vector<ld> dist(n+1, INF);
dist[0] = 0;
priority_queue<pair<ld, int>> que;
vector<bool> vis(n, false);
que.push({0, 0});
while (!que.empty()) {
auto [_, v] = que.top();
que.pop();
if (vis[v]) {
continue;
}
vis[v] = true;
for (int i = 1; i <= n; i++) {
// dbg(v, i, get(v, i), dist);
ld val = get(v, i);
if (dist[i] > dist[v] + val) {
dist[i] = dist[v] + val;
que.push({-dist[i], i});
}
}
}
// dbg(dist);
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) {
cout << -1 << '\n';
continue;
}
cout << dist[i] << '\n';
}
}
int main() {
setIO();
int tt = 1;
#ifdef TEST_CASES
cin >> tt;
#endif
while (tt--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3844kb
input:
5 3 0 0 3 0 10 10 0 -3 1 1 -1 -1 16 1 -1 0 100 100 100 100 -100 -3 10 0
output:
2.626226552146786 0.000000000000000 3.292893218813452 -1 14.285714285714286
result:
wrong answer 3rd numbers differ - expected: '3.0000000', found: '3.2928932', error = '0.0976311'