QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#813940 | #9869. Horizon Scanning | propane# | WA | 30ms | 3876kb | C++20 | 2.0kb | 2024-12-14 13:48:56 | 2024-12-14 13:48:58 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
using LL = long long;
const long double pi = acos(-1);
int sign(int x){
if (x > 0) return 1;
if (x < 0) return -1;
return 0;
}
struct Point{
LL x, y;
long double angle(){
return atan2(y, x);
}
LL operator^(const Point &t) const {
return x * t.y - y * t.x;
}
LL operator*(const Point &t) const {
return x * t.x + y * t.y;
}
int quad() const {
if (y < 0) return 1;
if (y > 0) return 3;
if (x > 0) return 2;
return 4;
};
bool operator<(const Point &t) const {
int q1 = quad(), q2 = t.quad();
if (q1 != q2) return q1 < q2;
return (*this ^ t) > 0;
}
bool operator==(const Point &t) const {
int q1 = quad(), q2 = t.quad();
return q1 == q2 and (*this ^ t) == 0;
}
long double len(){
return sqrtl(x * x + y * y);
}
};
long double a(Point a, Point b){
long double alpha = acosl(a * b / a.len() / b.len());
if ((a ^ b) >= 0) return alpha;
return 2 * pi - alpha;
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cout << fixed << setprecision(10);
int T;
cin >> T;
while(T--){
int n, k;
cin >> n >> k;
vector<Point> p(n);
for(int i = 0; i < n; i++){
cin >> p[i].x >> p[i].y;
}
sort(p.begin(), p.end());
long double ans = 0;
for(int i = 0; i < n; i++){
while(i + 1 < n and p[i] == p[i + 1]) i++;
if (p[i] == p[(i + k) % n]){
ans = pi * 2;
}
else{
ans = max(ans, a(p[i], p[(i + k) % n]));
}
}
cout << ans << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
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: 30ms
memory: 3876kb
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 314th numbers differ - expected: '3.1415927', found: '2.9996956', error = '0.0451672'