QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90680#6124. King Of Zombiesqgoi_official#WA 10ms3660kbC++142.8kb2023-03-24 18:06:592023-03-24 18:07:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-24 18:07:03]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3660kb
  • [2023-03-24 18:06:59]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define double long double

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3544kb

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: 3500kb

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: 10ms
memory: 3660kb

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:

2.76152626
0.38034666
0.00000000
0.86638320
0.00000000
0.86638320
0.18088887
0.86638320
0.18088887
0.38034666
0.38034666
0.86638320
0.10690147
0.00000000
1.54380826
0.10690147
0.00000000
0.71637051
0.00000000
0.00000000
0.86638320
0.00000000
0.86638320
0.86638320
0.00000000
0.71637051
0.25379604
0.0...

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '2.7615263', error = '2.7615263'