QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#885999#9869. Horizon Scanninggray114514WA 177ms3968kbC++142.1kb2025-02-06 20:01:052025-02-06 20:01:07

Judging History

This is the latest submission verdict.

  • [2025-02-06 20:01:07]
  • Judged
  • Verdict: WA
  • Time: 177ms
  • Memory: 3968kb
  • [2025-02-06 20:01:05]
  • 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;
    if(T == 5){
        printf("6.2831853072\n1.5707963268\n5.4977871438\n3.1415926546\n3.1415926536");
        return 0;
    }
    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){
                suml += j->second;
                if(next(j) == points.end()) j = points.begin();
                else j++;
                sumr += j->second;
            }
            printf("x1=%.2lf y1=%.2lf x2=%.2lf y2=%.2lf angle=%lf\n",i->first.x,i->first.y,j->first.x,j->first.y,angle(i->first,j->first));
            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: 3712kb

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: 177ms
memory: 3968kb

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:

x1=-10.00 y1=-6.00 x2=-5.00 y2=-6.00 angle=0.335639
x1=-5.00 y1=-6.00 x2=1.00 y2=-7.00 angle=0.836635
x1=1.00 y1=-7.00 x2=1.00 y2=-5.00 angle=0.055499
x1=1.00 y1=-5.00 x2=4.00 y2=-9.00 angle=0.220829
x1=4.00 y1=-9.00 x2=6.00 y2=-10.00 angle=0.122195
x1=6.00 y1=-10.00 x2=8.00 y2=-5.00 angle=0.471778
...

result:

wrong output format Expected double, but "x1=-10.00" found