QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#886090 | #9869. Horizon Scanning | gray114514 | WA | 127ms | 4096kb | C++14 | 1.8kb | 2025-02-06 20:30:12 | 2025-02-06 20:30:16 |
Judging History
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 ;
}
};
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;
while(T--){
cin >> n >> k;
for(int i=0,x,y;i<n;i++){
cin >> x >> y;
if(!points.count(point(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;
}
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: 4096kb
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.283185307 1.570796327 5.497787144 3.141592654 3.141592654
result:
ok 5 numbers
Test #2:
score: -100
Wrong Answer
time: 127ms
memory: 4096kb
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.692991497 2.922923708 4.652758267 2.772633107 5.742765807 4.857698991 3.419892313 2.812799962 6.283185307 6.283185307 2.402672622 6.146782703 3.842089024 2.342496717 4.601731759 6.283185307 3.036426530 3.324703471 5.608444365 5.672459343 1.673877935 1.114190855 2.408777552 6.283185307 3.061762668 ...
result:
wrong answer 2nd numbers differ - expected: '2.5748634', found: '2.9229237', error = '0.1351762'