QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#812970 | #9869. Horizon Scanning | test_algth | WA | 1ms | 4164kb | C++17 | 2.2kb | 2024-12-13 20:11:08 | 2024-12-13 20:11:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const double Pi = acos(-1);
const double eps = 1e-10;
template <class T>
inline void read(T &x) {
x = 0; int f = 1;
char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
x = x * f;
}
const int MAXN = 4e5;
struct node {
int x, y;
}a[MAXN + 10];
inline long long len(node x) {
return 1ll * x.x * x.x + 1ll * x.y * x.y;
}
inline bool cmp(const node &x, const node &y) {
if (fabs(atan2(x.y, x.x) - atan2(y.y, y.x)) < eps) return len(x) < len(y);
return atan2(x.y, x.x) < atan2(y.y, y.x);
}
/*
int chk(double r) {
for (int i = 1; i <= n; ++i) {
if
}
}*/
int main() {
// freopen ("std.in", "r", stdin);
// freopen ("std.out", "w", stdout);
int T; read(T);
while (T--) {
int n, K;
read(n); read(K);
for (int i = 1; i <= n; ++i) {
read(a[i].x);
read(a[i].y);
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; ++i) a[n + i] = a[i];
double ans = 0;
for (int i = 1; i <= n; ++i) {
// std::cout <<
double al = atan2(a[i].y, a[i].x);
double ar = atan2(a[i + K].y, a[i + K].x);
if (fabs(al - ar) < eps) {
if (len(a[i]) <= len(a[i + K]))
ans = max(ans, fabs(ar - al));
else {
ans = max(ans, 2 * Pi - fabs(al - ar));
}
} else {
//if (1ll * a[i].x * a[i + K].y + 1ll * a[i].y * a[i + K].x > 0)
if (al <= ar)
ans = max(ans, fabs(al - ar));
else ans = max(ans, 2 * Pi - fabs(al - ar));
}
}
printf("%.10f\n", ans);
/*
double l = 0, r = 2 * Pi;
while ((r - l) > eps) {
double mid = (l + r) / 2.0;
if (chk(mid) >= K) l = mid;
else r = mid;
}
printf("%.8f", l);*/
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4164kb
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:
0.0000000000 1.5707963268 5.4977871438 3.1415926546 3.1415926536
result:
wrong answer 1st numbers differ - expected: '6.2831853', found: '0.0000000', error = '1.0000000'