QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#734722 | #9576. Ordainer of Inexorable Judgment | propane | WA | 0ms | 4400kb | C++20 | 3.0kb | 2024-11-11 14:36:30 | 2024-11-11 14:36:30 |
Judging History
你现在查看的是最新测评结果
- [2024-12-23 14:23:26]
- hack成功,自动添加数据
- (/hack/1303)
- [2024-12-06 11:32:56]
- hack成功,自动添加数据
- (/hack/1271)
- [2024-11-14 21:58:28]
- hack成功,自动添加数据
- (/hack/1181)
- [2024-11-11 14:36:30]
- 提交
answer
#include<iostream>
#include<vector>
#include<cmath>
#include<iomanip>
#include<algorithm>
using namespace std;
using LL = long long;
struct Point{
double x, y;
Point operator+(Point t){
return {x + t.x, y + t.y};
}
double operator*(Point t){
return x * t.x + y * t.y;
}
Point operator-(Point t){
return {x - t.x, y - t.y};
}
Point operator*(double a){
return {x * a, y * a};
}
Point operator/(double a){
return {x / a, y / a};
}
double operator^(Point t) {
return x * t.y - y * t.x;
}
};
struct line{
Point p, v;
Point inter(line a) {
return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v));
}
};
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);
const double pi = acos(-1), eps = 1e-10;
int n, x0, y0, d, t;
cin >> n >> x0 >> y0 >> d >> t;
// [0, 2pi)
auto norm = [&](double x){
while(x < 0) x += 2 * pi;
while(x >= 2 * pi) x -= 2 * pi;
return x;
};
vector<double> cand;
vector<Point> p(n);
for(int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
if (x * x + y * y <= d * d){
cout << t << '\n';
return 0;
}
p[i] = {1.0 * x, 1.0 * y};
double len = sqrt(x * x + y * y);
double a = atan2(y, x);
double cosa = d / len;
double b = acos(cosa);
cand.push_back(norm(a - b));
cand.push_back(norm(a + b));
}
cand.push_back(0);
cand.push_back(2 * pi);
sort(cand.begin(), cand.end());
auto check = [&](double a){
Point v{cos(a), sin(a)};
for(auto pt : p){
if (pt * v > -eps and abs(pt ^ v) < d - eps) return true;
}
line l1 = {{0, 0}, v};
for(int i = 0; i < n; i++){
line l2 = {p[i], (p[(i + 1) % n] - p[i])};
if (abs(l1.v ^ l2.v) < eps) continue;
Point o = l1.inter(l2);
if (o * v > 0 and ((o - p[i]) * (o - p[(i + 1) % n])) < eps) return true;
}
return false;
};
// [st, st + t]
double st = norm(atan2(y0, x0));
int cnt = t / (2 * pi);
double remain = t - cnt * (2 * pi);
// [st, st + t]
auto inter = [&](double l1, double r1, double l2, double r2){
double l = max(l1, l2);
double r = min(r1, r2);
if (l > r) return 0.0;
return r - l;
};
double ans = 0;
for(int i = 0; i + 1 < cand.size(); i++){
if (check((cand[i] + cand[i + 1]) / 2)){
ans += cnt * (cand[i + 1] - cand[i]);
ans += inter(cand[i], cand[i + 1], st, st + remain);
ans += inter(cand[i], cand[i + 1], st - 2 * pi, st + remain - 2 * pi);
}
}
cout << fixed << setprecision(20) << ans << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4400kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
1.00000000000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4296kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.57079632679489655800
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4284kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.70775225747547665378
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 4280kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
0.00000000000000000000
result:
wrong answer 1st numbers differ - expected: '0.3842413', found: '0.0000000', error = '0.3842413'