QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#812272 | #9869. Horizon Scanning | Time_South | WA | 28ms | 4216kb | C++20 | 1.9kb | 2024-12-13 13:37:51 | 2024-12-13 13:37:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX (int)1e6+50
#define PI acos(-1.0)
struct point {
ll x, y;
}p[MAX];
// 计算向量的点积
ll pmul(point p1, point p2) {
return p1.x * p2.x + p1.y * p2.y;
}
// 计算向量的模长
double dis(point p) {
return sqrt(p.x * p.x + p.y * p.y);
}
// 计算两向量的叉积
ll xmul(point p1, point p2) {
return p1.x * p2.y - p1.y * p2.x;
}
int xx(point a) //判断象限
{
if (a.x > 0 && a.y >= 0)return 1;
if (a.x <= 0 && a.y > 0)return 2;
if (a.x < 0 && a.y <= 0)return 3;
if (a.x >= 0 && a.y < 0)return 4;
}
bool cmp(point a, point b) //先按象限从小到大排序 再按极角从小到大排序
{
if (xx(a) == xx(b)) return xmul(a, b) > 0; //逆时针排序
else return xx(a) < xx(b);
}
// 计算两向量间的夹角(以弧度表示,范围为 [0, 2 * pi])
double angle_vec(point p1, point p2) {
double res = atan2(p2.y, p2.x) - atan2(p1.y, p1.x);
if (res < 0)
res += 2 * PI;
return res;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, k, i, j;
cin >> n >> k;
for (i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y;
//p[i + n] = p[i];
}
double res = 0;
if (n == k) {
res = 2 * PI;
cout << fixed << setprecision(10) << res << '\n';
continue;
}
sort(p, p + n, cmp);
//for (i = 0; i < n; i++) {
// cout << p[i].x << ' ' << p[i].y << '\n';
//}
for (i = 0; i < n; i++) {
p[i + n] = p[i];
}
for (i = 0; i < n; i++) {
res = max(res, angle_vec(p[i], p[i + k]));
}
cout << fixed << setprecision(10) << res << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4124kb
input:
5 1 1 0 1 8 2 1 0 1 1 0 1 -1 1 -1 0 -1 -1 0 -1 1 -1 4 2 -1 1 0 1 0 2 1 1 4 2 -1000000000 0 -998244353 1 998244353 1 1000000000 0 3 1 0 1 0 2 0 -1
output:
6.2831853072 1.5707963268 5.4977871438 3.1415926546 3.1415926536
result:
ok 5 numbers
Test #2:
score: -100
Wrong Answer
time: 28ms
memory: 4216kb
input:
10000 16 1 -10 -6 -5 -6 -4 9 -2 5 -2 10 1 -7 1 -5 1 6 3 1 4 -9 6 -10 6 -3 6 1 8 -5 8 -4 9 -4 17 4 -9 2 -8 -4 -8 -3 -8 -1 -6 -2 -6 -1 -6 8 -5 -8 -5 10 -4 8 -2 -8 4 -9 4 0 5 -3 8 -5 9 -2 10 10 10 6 -7 2 -4 6 -2 -7 -2 -1 -1 7 1 -9 1 8 3 -4 7 -4 9 -2 14 3 -9 10 -8 -10 -8 -8 -6 -7 -6 -5 -1 -7 -1 -2 0 -1 ...
output:
1.6929914975 2.5748634361 4.6527582673 2.7726331074 5.7427658069 4.8576989910 3.4198923126 2.8127999621 6.2831853072 6.2831853072 5.1172807667 6.1467827028 3.8420890235 2.3424967168 3.4633432080 6.2831853072 5.9614347528 3.3247034709 5.2627749281 5.6724593428 1.6738779353 1.1141908549 2.4087775518 6...
result:
wrong answer 42nd numbers differ - expected: '6.2831853', found: '6.2599337', error = '0.0037006'