QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#809691 | #9869. Horizon Scanning | TDXIAO | WA | 1ms | 4128kb | C++20 | 2.3kb | 2024-12-11 16:46:38 | 2024-12-11 16:46:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const double pi = acos(-1);
struct Point{
ll x, y;
};
int operator^(const Point &a, const Point &b){
return a.x * b.y - a.y * b.x;
}
int quad(const Point &a){
if(a.x > 0 && a.y == 0){
return 1;
}else if(a.x > 0 && a.y > 0){
return 2;
}else if(a.x == 0 && a.y > 0){
return 3;
}else if(a.x < 0 && a.y > 0){
return 4;
}else if(a.x < 0 && a.y == 0){
return 5;
}else if(a.x < 0 && a.y < 0){
return 6;
}else if(a.x == 0 && a.y < 0){
return 7;
}else if(a.x > 0 && a.y < 0){
return 8;
}
}
bool cmp(const Point &a, const Point &b){
int qa = quad(a), qb = quad(b);
if(qa != qb){
return qa < qb;
}else{
return (a ^ b) > 0;
}
}
double fun(Point &p) {
auto [x, y] = p;
if (x > 0) {
if (y > 0) {
return atan(y/x);
} else if (y == 0) {
return atan(y/x);
} else {
return atan(x/(-y)) + pi*3/2;
}
} else if (x == 0) {
if (y > 0) {
return pi/2;
} else {
return pi*3/2;
}
} else {
if (y > 0) {
return atan((-x)/y) + pi/2;
} else if (y == 0) {
return pi;
} else {
return atan((-x)/(-y)) + pi;
}
}
}
void solve() {
int n, k;
cin>>n>>k;
vector<Point> a(2*n+1);
for (int i = 1; i <= n; i++) {
ll x, y;
cin>>x>>y;
a[i] = {x, y};
}
sort(a.begin(), a.begin()+n+1, cmp);
// for (int i = 1; i <= n; i++) {
// printf("x = %lld, y = %lld\n", a[i].x, a[i].y);
// }
// printf("\n");
for (int i = 1; i <= n; i++) {
a[i+n] = a[i];
}
double ans = 0;
for (int i = 1; i <= n; i++) {
double l = fun(a[i]);
double r = fun(a[i+k]);
if (i+k > n) r += 2*pi;
// printf("i = %d, l = %lf, r = %lf, f = %lf\n", i, l, r, r-l);
ans = max(ans, r-l);
}
cout<<fixed<<setprecision(20);
cout<<ans<<'\n';
}
int main()
{
if (ifstream("test.in")) {
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
}
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin>>T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4128kb
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.28318530717958623200 2.35619449019234483700 5.49778714378213795300 4.71238897938293099799 3.14159265358979311600
result:
wrong answer 2nd numbers differ - expected: '1.5707963', found: '2.3561945', error = '0.5000000'