QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#812970#9869. Horizon Scanningtest_algthWA 1ms4164kbC++172.2kb2024-12-13 20:11:082024-12-13 20:11:11

Judging History

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

  • [2024-12-13 20:11:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4164kb
  • [2024-12-13 20:11:08]
  • 提交

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'