QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90676 | #6124. King Of Zombies | qgoi_official# | WA | 9ms | 3656kb | C++14 | 2.8kb | 2023-03-24 17:47:51 | 2023-03-24 17:47:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
register int s = 0, f = 1; register char ch = getchar();
while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
return s * f;
}
struct node {
int x, y;
inline node() { }
inline node(int X, int Y) : x(X), y(Y) { }
inline ll mo() { return 1ll * x * x + 1ll * y * y; }
inline double len() { return sqrt(mo()); }
};
const double inf = 1e18;
const int N = 1005;
#define eps 1e-7
template<class T> inline T abs_(T a) { return a < 0 ? -a : a; }
inline node operator + (node a, node b) { return node(a.x + b.x, a.y + b.y); }
inline node operator - (node a, node b) { return node(a.x - b.x, a.y - b.y); }
inline ll operator ^ (node a, node b) { return 1ll * a.x * b.y - 1ll * a.y * b.x; }
inline node operator * (int k, node b) { return node(k * b.x, k * b.y); }
inline int sgn(int x) { return x < 0 ? -1 : (x > 0); }
inline int dcmp(double x) { return abs_(x) < eps ? 0 : (x < 0 ? -1 : 1); }
inline bool operator == (node a, node b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }
inline double dis(node a, node p, node q) { return p == q ? 0 : (1.0 * abs_((a - p) ^ (a - q)) / (p - q).len()); }
inline pair<double, double> calc(node a, node b, node v, int r) {
if ((a - b).mo() <= 1ll * r * r) {
if (v.x == 0 && v.y == 0) return make_pair(0.0, 0.0);
double d = dis(a, b - v, b + v);
double l1 = sqrt(1.0 * (a - b).mo() - d * d), l2 = sqrt(1.0 * r * r - d * d);
return make_pair(0.0, (l1 + l2) / v.len());
}
if (!(sgn(a.x - b.x - r) <= sgn(v.x) && sgn(v.x) <= sgn(a.x - b.x + r)) ||
!(sgn(a.y - b.y - r) <= sgn(v.y) && sgn(v.y) <= sgn(a.y - b.y + r))) return make_pair(-1.0, -1.0);
double d = dis(a, b - v, b + v);
if (dcmp(d - r) > 0) return make_pair(-1.0, -1.0);
double l1 = sqrt(1.0 * (a - b).mo() - d * d), l2 = sqrt(1.0 * r * r - d * d);
return make_pair((l1 - l2) / v.len(), (l1 + l2) / v.len());
}
double f[N];
bool vis[N];
node p[N], v[N];
int n, r;
int main() {
n = read(); r = read();
for (int i = 0; i <= n; ++i) {
p[i].x = read(); p[i].y = read();
v[i].x = read(); v[i].y = read();
f[i] = inf;
} f[0] = 0;
for (int i = 0; i <= n; ++i) {
int x = -1; double y = inf - 1;
for (int j = 0; j <= n; ++j) {
if (vis[j] || dcmp(y - f[j]) < 0) continue;
x = j; break;
} vis[x] = 1;
for (int j = 0; j <= n; ++j) {
if (vis[j]) continue;
pair<double, double> pr = calc(p[j], p[x], v[x] - v[j], r);
if (dcmp(pr.first) < 0) continue;
double l = pr.first, r = pr.second;
if (dcmp(l - f[x]) >= 0) f[j] = min(f[j], l);
else if (dcmp(r - f[x]) >= 0) f[j] = min(f[j], f[x]);
}
}
for (int i = 1; i <= n; ++i) printf("%.8lf\n", (dcmp(inf - f[i]) == 0) ? -1 : f[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3508kb
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.62622655 0.00000000 3.00000000 -1.00000000 14.28571429
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
4 10 0 0 0 0 10 0 0 0 20 0 0 0 30 0 0 0 41 0 0 0
output:
0.00000000 0.00000000 0.00000000 -1.00000000
result:
ok 4 numbers
Test #3:
score: -100
Wrong Answer
time: 9ms
memory: 3536kb
input:
814 5261 8674 -10000 83 9959 -3135 4963 -5450 -980 -6718 -5021 -5412 1206 8906 -9471 -4357 5471 -3795 2180 -4645 -2664 9110 -5528 9221 -3130 -3916 1465 -6825 5446 1767 -3479 -6871 -7960 -3523 5303 -1141 7806 3362 -3357 7529 -6106 -7323 -8776 3458 3288 -4825 -5940 -4857 95 -3169 6767 -3056 -2340 3228...
output:
-1.00000000 -1.00000000 0.00000000 -1.00000000 0.00000000 -1.00000000 -1.00000000 -1.00000000 0.18088887 1.48806282 -1.00000000 -1.00000000 0.10690147 0.00000000 1.54380826 0.10690147 0.00000000 0.71637051 0.00000000 0.00000000 -1.00000000 0.00000000 -1.00000000 2.42280897 0.00000000 0.71637051 0.25...
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '-1.0000000', error = '1.0000000'