QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#809410 | #9869. Horizon Scanning | ucup-team4479# | WA | 28ms | 7260kb | C++23 | 2.0kb | 2024-12-11 14:53:05 | 2024-12-11 14:53:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int N=200005;
const long double PI=acosl(-1);
constexpr long double eps=1e-10;
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(cur<-eps) 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: 0ms
memory: 6200kb
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: 28ms
memory: 7260kb
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.5748634361 4.6527582673 2.7726331074 5.7427658069 4.8576989910 3.4198923126 2.8127999621 6.2831853072 6.2831853072 5.1172807667 6.1467827028 3.8420890235 2.3424967168 3.4633432080 6.2831853072 5.9614347528 3.3247034709 5.2627749281 5.6724593428 1.6738779353 1.1141908549 2.4087775518 6...
result:
wrong answer 42nd numbers differ - expected: '6.2831853', found: '6.2599337', error = '0.0037006'