QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#809424#9869. Horizon Scanningucup-team4479#WA 29ms7260kbC++232.0kb2024-12-11 14:58:532024-12-11 14:58:53

Judging History

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

  • [2024-12-11 14:58:53]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:7260kb
  • [2024-12-11 14:58:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=200005;
const long double PI=acosl(-1);
constexpr long double eps=1e-15;
class Point
{
public:
    int x,y;
    Point(){x=0,y=0;}
    Point(const int &_x,const int &_y):x(_x),y(_y) {}
    friend Point operator + (const Point &a,const Point &b)
    {
        return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b)
    {
        return Point(a.x-b.x,a.y-b.y);
    }
    friend long long cross(const Point &a,const Point &b)
    {
        return (long long)a.x*b.y-(long long)a.y*b.x;
    }
    friend long long dot(const Point &a,const Point &b)
    {
        return (long long)a.x*b.x+(long long)a.y*b.y;
    }
    long double angle()const
    {
        return atan2l(y,x);
    }
    int quadrant()const
    {
        if(x>0&&y>=0) return 1;
        else if(x<=0&&y>0) return 2;
        else if(x<0&&y<=0) return 3;
        else if(x>=0&&y<0) return 4;
        else return 0;
    }
    long double length()const
    {
        return sqrtl((long long)x*x+(long long)y*y);
    }
};
bool cmp_polar_angle(const Point &a,const Point &b)
{
    int x=a.quadrant(),y=b.quadrant();
    if(x!=y) return x<y;
    return cross(a,b)>0;
}
int n,k;
Point p[N];
long double d[N];
void solve()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>p[i].x>>p[i].y;
    sort(p,p+n,cmp_polar_angle);
    if(k==n)
    {
        long double ans=PI*2;
        cout<<fixed<<setprecision(10)<<ans<<"\n";
        return;
    }
    for(int i=0;i<n;i++)
    {
        d[i]=p[i].angle();
        if(d[i]<-eps) d[i]+=PI*2;
    }
    long double ans=0;
    for(int i=0;i<n;i++)
    {
        int j=(i+k)%n;
        long double cur=d[j]-d[i];
        if(cross(p[i],p[j])<0) cur+=PI*2;
        ans=max(ans,cur);
    }
    cout<<fixed<<setprecision(10)<<ans<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7260kb

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: 29ms
memory: 5464kb

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.6929914975
2.2142974356
9.9263820150
2.7726331074
11.3173248420
10.2404698841
9.7030776198
2.8127999621
6.2831853072
6.2831853072
11.1971020553
12.0832449495
10.1252743307
2.0344439358
9.7465285152
6.2831853072
11.3348669020
3.3247034709
11.5459602352
11.1374713422
1.6738779353
1.1141908549
2.4087...

result:

wrong answer 2nd numbers differ - expected: '2.5748634', found: '2.2142974', error = '0.1400331'