QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#885907#9869. Horizon Scanninggray114514WA 95ms4096kbC++142.0kb2025-02-06 19:31:392025-02-06 19:31:39

Judging History

This is the latest submission verdict.

  • [2025-02-06 19:31:39]
  • Judged
  • Verdict: WA
  • Time: 95ms
  • Memory: 4096kb
  • [2025-02-06 19:31:39]
  • Submitted

answer

#include <cmath>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
#define PI acos(-1)
#define eqs 1e-8
struct point{
    double x,y;
    point(double _x=0,double _y=0) : x(_x) , y(_y) {}

    bool operator<(const point& other) const {
        double angle1 = atan2(y,x) , angle2 = atan2(other.y,other.x) ;
        return angle1 < angle2 ;
    }
    bool operator==(const point& other) const {
        double angle1 = atan2(y,x) , angle2 = atan2(other.y,other.x) ;
        return fabs(angle1 - angle2) < eqs ;
        //return angle1 == angle2;
    }
};
constexpr int N = 2e5+10;
map<point,int> points ;
double angle(point A,point B)
{
    double res = acos((A.x*B.x+A.y*B.y) / sqrt(A.x*A.x+A.y*A.y) / sqrt(B.x*B.x+B.y*B.y)) ;
    double area = A.x * B.y - A.y * B.x;
    if(area >= 0)    return res;
    else return 2*PI - res;
}
int main()
{
    int T,n,k;
    cin >> T;
    while(T--){
        cin >> n >> k;
        for(int i=0,x,y;i<n;i++){
            cin >> x >> y;
            points[point(x,y)]++;
        }
        if(n == k){
            printf("%.9lf\n",PI*2);
            continue;
        }
        double ans = 0;
        int sz = points.size() , suml(0) , sumr(points.begin()->second);
        for(auto i=points.begin(),j=points.begin();i != points.end();i++){
            sumr -= i->second;
            while(suml < k || sumr < k){
                if(next(j) == points.end()) j = points.begin();
                else j++;
                suml += (j == points.begin() ? points.rbegin()->second : prev(j)->second);
                sumr += j->second;
            }
         //   printf("x1=%.2lf y1=%.2lf x2=%.2lf y2=%.2lf\n",i->first.x,i->first.y,j->first.x,j->first.y);
            if(i == j){
                ans = 2*PI;
                break;
            }
            ans = max(ans,angle(i->first,j->first));
            suml -= i->second;
        }
        printf("%.9lf\n",ans);
        points.clear();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4096kb

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.283185307
1.570796327
5.497787144
3.141592654
3.141592654

result:

ok 5 numbers

Test #2:

score: -100
Wrong Answer
time: 95ms
memory: 4096kb

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.692991497
2.574863436
4.652758267
2.772633107
5.742765807
4.857698991
3.419892313
2.812799962
6.283185307
6.283185307
1.849095986
6.146782703
3.842089024
2.342496717
3.463343208
6.283185307
3.036426530
3.324703471
5.262774928
5.672459343
1.673877935
1.114190855
2.408777552
6.283185307
3.061762668
...

result:

wrong answer 11th numbers differ - expected: '5.1172808', found: '1.8490960', error = '0.6386565'