QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#809742 | #9869. Horizon Scanning | TDXIAO | WA | 27ms | 4112kb | C++20 | 2.7kb | 2024-12-11 17:03:03 | 2024-12-11 17:03:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const double pi = acos(-1);
struct Point{
ll x, y;
Point(){}
Point(ll _x, ll _y){x = _x, y=_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 0;
} 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 pi + pi/2 - atan((-x)/(-y));
}
}
}
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};
}
vector<double> b(2*n+1);
for (int i = 1; i <= n; i++) {
b[i] = fun(a[i]);
}
sort(b.begin()+1, b.begin()+n+1);
for (int i = 1; i <= n; i++) {
b[i+n] = b[i]+2*pi;
}
sort(a.begin()+1, 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");
// cout<<fun(Point(1, -1))<<'\n';
// cout<<fun(Point(2, -1))<<'\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;
l = b[i];
r = b[i+k];
// 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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4092kb
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 1.57079632679489655800 5.49778714378213795300 3.14159265459155179201 3.14159265358979311600
result:
ok 5 numbers
Test #2:
score: -100
Wrong Answer
time: 27ms
memory: 4112kb
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:
2.35619449019234483700 2.35619449019234483700 4.95736764351155390074 3.14159265358979311600 5.49778714378213884117 4.85769899102039204308 3.92699081698724139500 3.46334320798643524597 6.28318530717958623200 6.28318530717958712017 5.49778714378213795300 6.28318530717958712017 3.60524026259059926502 2...
result:
wrong answer 1st numbers differ - expected: '1.6929915', found: '2.3561945', error = '0.3917344'