QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#813930#9869. Horizon Scanningpropane#WA 1ms4120kbC++201.9kb2024-12-14 13:43:232024-12-14 13:43:24

Judging History

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

  • [2024-12-14 13:43:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4120kb
  • [2024-12-14 13:43:23]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
using LL = long long;
const double pi = acos(-1); 

struct Point{
    LL x, y;

    double angle(){
        return atan2(y, x);
    }

    LL operator^(const Point &t) const {
        return x * t.y - y * t.x;
    }

    LL operator*(const Point &t) const {
        return x * t.x + y * t.y;
    }

    int quad() const {
        if (y < 0) return 1;
        if (y > 0) return 3;
        if (x > 0) return 2;
        return 4;
    };

    bool operator<(const Point &t) const {
        int q1 = quad(), q2 = t.quad();
        if (q1 != q2) return q1 < q2;
        return (*this ^ t) > 0;
    }

    bool operator==(const Point &t) const {
        int q1 = quad(), q2 = t.quad();
        return q1 == q2 and (*this ^ t) == 0;
    }

    double len(){
        return sqrtl(x * x + y * y);
    }

};

double a(Point a, Point b){
    double alpha = acos(a * b / a.len() / b.len());
    if ((a ^ b) >= 0) return alpha;
    return 2 * pi - alpha;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(10);

    int T;
    cin >> T;
    while(T--){
        int n, k;
        cin >> n >> k;
        vector<Point> p(n);
        for(int i = 0; i < n; i++){
            cin >> p[i].x >> p[i].y;
        }
        sort(p.begin(), p.end());
        double ans = 0;
        for(int i = 0; i < n; i++){
            while(i < n and p[i] == p[i + 1]) i++;
            if (p[i] == p[(i + k) % n]){
                ans = pi * 2;
            }
            else{
                ans = max(ans, a(p[i], p[(i + k) % n]));
            }
        }
        cout << ans << '\n';
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4120kb

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.1415926536
6.2831853072

result:

wrong answer 5th numbers differ - expected: '3.1415927', found: '6.2831853', error = '1.0000000'