QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#728941#9576. Ordainer of Inexorable Judgmentucup-team5062#WA 1ms4248kbC++173.0kb2024-11-09 16:14:562024-11-09 16:14:57

Judging History

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

  • [2024-12-23 14:23:26]
  • hack成功,自动添加数据
  • (/hack/1303)
  • [2024-12-06 11:32:56]
  • hack成功,自动添加数据
  • (/hack/1271)
  • [2024-11-14 21:58:28]
  • hack成功,自动添加数据
  • (/hack/1181)
  • [2024-11-09 16:14:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4248kb
  • [2024-11-09 16:14:56]
  • 提交

answer

#include <array>
#include <cmath>
#include <vector>
#include <complex>
#include <iostream>
#include <algorithm>
using namespace std;

const long double pi = acos(-1.0L);

using point = complex<long double>;

long double dot(const point& a, const point& b) {
	return (conj(a) * b).real();
}

long double cross(const point& a, const point& b) {
	return (conj(a) * b).imag();
}

array<point, 2> tangent(const point& p, const point& c, double r) {
	point v = (p - c) / abs(p - c);
	long double d = abs(p - c);
	long double t = r * r / d;
	array<point, 2> res;
	res[0] = c + (t - point(0, 1) * sqrt(r * r - t * t)) * v;
	res[1] = c + (t + point(0, 1) * sqrt(r * r - t * t)) * v;
	return res;
}

// half-line: (0, 0) towards z
// segment: s0-s1
bool intersect(const point& z, const point& s0, const point& s1) {
	point v0 = s0, v1 = s1;
	long double t0 = cross(z, v0);
	long double t1 = cross(z, v1);
	if (t0 > t1) {
		swap(t0, t1);
		swap(v0, v1);
	}
	if (t0 > 0 || t1 < 0) {
		return false;
	}
	if (t0 == 0 && dot(z, v0) >= 0) {
		return true;
	}
	if (t1 == 0 && dot(z, v1) >= 0) {
		return true;
	}
	if (t0 == 0 || t1 == 0) {
		return false;
	}
	return cross(v0, v1) > 0;
}

// half-line: (0, 0) towards z
// point: p
long double distance(const point& z, const point& p) {
	if (dot(z, p) < 0) {
		return abs(p);
	}
	return abs(cross(z, p)) / abs(z);
}

// half-line: (0, 0) towards z
// segment: s0-s1
long double distance(const point& z, const point& s0, const point& s1) {
	if (intersect(z, s0, s1)) {
		return 0.0;
	}
	long double res1 = distance(z, s0);
	long double res2 = distance(z, s1);
	return min(res1, res2);
}

int main() {
	// step #1. input
	auto read_point = []() -> point {
		long double x, y;
		cin >> x >> y;
		return point(x, y);
	};
	int N, D, T;
	cin >> N;
	point V = read_point();
	cin >> D >> T;
	vector<point> G(N);
	for (int i = 0; i < N; i++) {
		G[i] = read_point();
	}
	G.push_back(G[0]);

	// step #2. calculate candidates
	vector<long double> v;
	for (int i = 0; i < N; i++) {
		array<point, 2> res = tangent(G[i], point(0, 0), D);
		v.push_back(arg(res[0]));
		v.push_back(arg(res[1]));
	}
	sort(v.begin(), v.end());
	v.push_back(v[0] + 2 * pi);

	// step #3. calculate "validity"
	vector<bool> ok(2 * N, false);
	for (int i = 0; i < 2 * N; i++) {
		point z = polar(1.0L, (v[i] + v[i + 1]) / 2);
		for (int j = 0; j < N; j++) {
			long double d = distance(z, G[j], G[j + 1]);
			if (d <= D) {
				ok[i] = true;
			}
		}
	}

	// step #4. calculate answer
	long double tl = arg(V);
	long double tr = tl + T;
	long double ans = 0.0;
	for (int i = 0; i < 2 * N; i++) {
		if (ok[i]) {
			long double pl = v[i] - 2 * pi, pr = v[i + 1] - 2 * pi;
			while (pl < tr) {
				long double ql = max(pl, tl);
				long double qr = min(pr, tr);
				if (ql < qr) {
					ans += qr - ql;
				}
				pl += 2 * pi;
				pr += 2 * pi;
			}
		}
	}

	// step #5. output
	cout.precision(15);
	cout << fixed << ans << endl;

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4248kb

input:

3 1 0 1 1
1 2
2 1
2 2

output:

1.000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4180kb

input:

3 1 0 1 2
1 2
2 1
2 2

output:

1.570796326794897

result:

ok found '1.5707963', expected '1.5707963', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4176kb

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.707752257475330

result:

ok found '2500.7077523', expected '2500.7077523', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 4192kb

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

4999.460466887865790

result:

wrong answer 1st numbers differ - expected: '0.3842413', found: '4999.4604669', error = '4999.0762256'