QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#817652 | #9869. Horizon Scanning | Susie_Rain | WA | 59ms | 4232kb | C++20 | 2.9kb | 2024-12-17 09:41:37 | 2024-12-17 09:41:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cout<<x<<"--------------------------------------\n" ;
const int N = 1e5 + 10;
typedef long long ll;
const int INF = 1e9 ;
const int MOD = 1e9 + 7 ;
typedef pair<int,int> PII ;
int gcd(int a,int b){
return b ? gcd(b,a%b) : a ;
}
ll qpow(int a,int k){
ll res = 1 ;
while (k){
if(k&1) res = 1ll * res * a % MOD ;
a = 1ll * a * a % MOD ;
k >>= 1 ;
}
return res ;
}
int n;
int k;
const double PI = acos(-1.0);
#define double long long
const double eps = 0;
inline int sgn(double x){
return fabs(x)<=eps?0:(x<0?-1:1);
}
struct point {
double x, y;
int id;
point(double a = 0, double b = 0, int c = 0): x(a), y(b), id(c) {
}
point operator +(const point &A) const {
return point(x + A.x, y + A.y);
}
point operator -(const point &A) const {
return point(x - A.x, y - A.y);
}
point operator *(const double v) const {
return point(x * v, y * v);
}
point operator /(const double v) const {
return point(x / v, y / v);
}
bool operator ==(const point &A) const {
return sgn(x - A.x) == 0 && sgn(y - A.y) == 0;
}
double norm() const {
return sqrt(x * x + y * y);
}
bool operator<(const point &a) const {
if (abs(x - a.x) <= eps) return y < a.y - eps;
return x < a.x - eps;
}
bool operator>(const point &a) const { return !(*this < a || *this == a); }
double operator^(const point &a) const { return x * a.y - y * a.x; } // 叉积,注意优先级
double operator*(const point &a) const { return x * a.x + y * a.y; }
int toleft(const point &a) const {
const auto t = (*this) ^ a;
return (t > eps) - (t < -eps);
} // to-left 测试
point rot(const double cosr, const double sinr) const { return {x * cosr - y * sinr, x * sinr + y * cosr}; }
// 逆时针旋转(给定角度的正弦与余弦)
};
bool cmp(point a,point b){
return (atan2(a.y,a.x) < atan2(b.y,b.x));
}
using Points = vector<point>;
#undef double
#define double long double
void solve(){
cin >> n >> k;
Points p(n);
for(int i=0;i<n;i++){
cin >> p[i].x >> p[i].y;
}
cout << fixed << setprecision(10);
if(n==k || n==1){
cout << 2.0 * PI << '\n';
return;
}
std::sort(p.begin(), p.end(),cmp);
double ans = 0;
for(int i=0;i<n;i++){
int j = (i+k) % n;
double t1 = atan2(p[i].y,p[i].x);
double t2 = atan2(p[j].y,p[j].x);
if(j<i){
if(t2-t1<0){
ans = max(ans,t2-t1+2*PI);
}
}
ans = max(ans,t2-t1);
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false) ;
cin.tie(0) ;
int tt = 1 ;
cin >> tt ;
while (tt--) solve() ;
return 0 ;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4232kb
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: 59ms
memory: 4148kb
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 42nd numbers differ - expected: '6.2831853', found: '6.2599337', error = '0.0037006'