QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#807401 | #9869. Horizon Scanning | Wzy# | WA | 20ms | 4344kb | C++14 | 1.5kb | 2024-12-09 22:44:46 | 2024-12-09 22:44:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const int N=2e5+10,M=2e6;
const int mod=998244353;
const LL P=1e9+7;
const LL INF=1e18;
LL h[N],e[M],ne[M],w[M],idx;
LL d[N];
int n;
LL tr[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL sum(int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
void solve(){
double pi=acos(-1);
int n,k;
cin>>n>>k;
vector<double> a(n);
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
if(x==0&&y>0) a[i]=pi/2;
else if(x==0) a[i]=pi*3/2;
else a[i]=atan(y/x);
if(x<0) a[i]+=pi;
else if(y<0&&x!=0) a[i]+=pi*2;
//if()
//cout<<a[i]<<endl;
}
sort(a.begin(),a.end());
//for(auto t:a) cout<<t<<endl;
//cout<<endl;
double res=0;
for(int i=0;i<n;i++){
if(i<n-1&&a[i]==a[i+1]) continue;
auto t=a[i];
int g;
if(n-i-1<k) g=k-(n-i-1)-1;
else g=i+k;
if(g<=i) res=max(res,2*pi-t+a[g]);
else res=max(res,a[g]-t);
//cout<<g<<" "<<res<<endl;
}
printf("%.10lf\n",res);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4144kb
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 3.1415926536
result:
ok 5 numbers
Test #2:
score: -100
Wrong Answer
time: 20ms
memory: 4344kb
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.4056476494 3.1415926536 4.5880339858 2.5535900500 6.2831853072 5.4977871438 3.4633432080 3.1415926536 6.2831853072 6.2831853072 5.4977871438 6.2831853072 4.0688878716 3.1415926536 3.9269908170 6.2831853072 6.2831853072 3.4078447027 5.4977871438 5.4977871438 2.3561944902 1.2490457724 3.1415926536 6...
result:
wrong answer 1st numbers differ - expected: '1.6929915', found: '1.4056476', error = '0.1697255'