QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187162#3854. RadarSocialZxy#WA 2ms5940kbC++141.6kb2023-09-24 15:03:052023-09-24 15:03:07

Judging History

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

  • [2023-09-24 15:03:07]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5940kb
  • [2023-09-24 15:03:05]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;

int get() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

const int N = 1e5 + 5;
int nr, nf, n;
int _r[N];
struct Vector {
	double x, y;
	double arc() { return atan2(y, x); }
	friend bool operator <(Vector a, Vector b) { return a.arc() < b.arc(); }
	friend double operator *(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
	double len() { return sqrt(*this * *this); }
} _l[N];

double GetDis(Vector a, int id, double r) {
	double arc = _l[id].arc();
	double x = cos(arc) * r, y = sin(arc) * r;
	return sqrt((a.x - x) * (a.x - x) + (a.y - y) * (a.y - y));
}

double GetMin(Vector a, int id) {
	double len = a * _l[id] / _l[id].len();
	int nxt = lower_bound(_r + 1, _r + 1 + nr, len) - _r;
	double ans = 1e18;
	if(nxt <= nr) ans = min(ans, GetDis(a, id, _r[nxt]));
	if(nxt > 1) ans = min(ans, GetDis(a, id, _r[nxt - 1]));
	return ans;
}

main() {
	nr = get(), nf = get(), n = get();
	for(int i = 1; i <= nr; i++) _r[i] = get();
	for(int i = 1; i <= nf; i++) _l[i].x = get(), _l[i].y = get();
	sort(_l + 1, _l + 1 + nf);
	_l[0] = _l[nf], _l[nf + 1] = _l[1];
	for(int i = 1; i <= n; i++) {
		Vector now;
		now.x = get(), now.y = get();
		int suf = lower_bound(_l + 1, _l + 1 + nf, now) - _l;
		double ans = 1e18;
		for(int i = -2; i <= 2; i++)
			ans = min(ans, GetMin(now, (suf + i + nf) % nf));
		printf("%.10Lf\n", ans);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 8 4
2
4
7
1 0
2 1
0 1
-1 1
-5 -2
-5 -6
-2 -7
6 -1
-1 -1
3 1
-5 -3
8 1

output:

0.6052910729
0.9777722905
1.5518451054
1.4142135624

result:

ok 4 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 5816kb

input:

1 8 32
7
0 1
1 0
0 -1
-1 0
1 -1
-1 1
-1 -1
1 1
20 10
10 20
-20 10
10 -20
-10 20
20 -10
-10 -20
-20 -10
2 1
1 2
-2 1
1 -2
-1 2
2 -1
-1 -2
-2 -1
5 0
0 5
-5 0
0 -5
5 5
5 -5
-5 5
-5 -5
9 0
0 9
-9 0
0 -9
9 9
9 -9
-9 9
-9 -9

output:

15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
2.0000000000
2.0000000000
2.0000000000
2.0000000000
0.0710678119
0.0710678119
0.0710...

result:

ok 32 numbers

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3848kb

input:

3 4 1681
16
8
4
-1 0
0 -1
0 1
1 0
-9 17
-4 -7
2 -13
-11 -17
15 -19
-7 1
-8 14
-8 -7
-8 20
-16 -3
12 14
-3 12
9 -5
-18 11
3 -1
2 0
-18 0
0 -19
-1 -19
18 -8
2 20
5 -8
-8 -19
-9 -16
20 -19
14 -1
3 10
-1 -4
4 10
16 17
19 -7
-17 4
1 -12
-5 -12
-5 -10
-15 -5
-10 -19
-2 -10
-4 -16
-2 4
-14 8
-17 16
4 1
16 ...

output:

15.8113883008
9.8488578018
9.2195444573
17.0293863659
21.2132034356
9.0553851381
12.8062484749
10.6301458127
17.8885438200
12.3693168769
15.6204993518
8.5440037453
7.0710678119
17.8044938148
13.0384048104
14.0000000000
14.0000000000
15.0000000000
15.0332963784
16.1245154966
16.1245154966
9.433981132...

result:

wrong answer 1st numbers differ - expected: '9.0553851', found: '15.8113883', error = '0.7460757'