QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#807401#9869. Horizon ScanningWzy#WA 20ms4344kbC++141.5kb2024-12-09 22:44:462024-12-09 22:44:47

Judging History

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

  • [2024-12-09 22:44:47]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:4344kb
  • [2024-12-09 22:44:46]
  • 提交

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'