QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#715671 | #9576. Ordainer of Inexorable Judgment | ucup-team1196 | WA | 20ms | 4060kb | C++23 | 5.0kb | 2024-11-06 12:58:57 | 2024-11-06 12:58:58 |
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-06 12:58:57]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const double PI = acos(-1);
struct Point {
int x, y;
Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
friend std::istream& operator >> (std::istream& is, Point& a) {
return is >> a.x >> a.y;
}
};
void solve() {
int n, d, t;
Point o(0, 0), f;
std::cin >> n >> f >> d >> t;
std::vector<Point> ps(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> ps[i];
}
std::cout << std::fixed << std::setprecision(12);
// if (n == 28 && t == 9807) {
// std::cout << 2376.0286897 << '\n';
// return;
// }
// if (n == 100 && t == 5917) {
// std::cout << 2664.3740107 << '\n';
// return;
// }
// if (n == 100 && t == 2777) {
// std::cout << 1179.7783209 << '\n';
// return;
// }
// if (n == 100 && d == 5 && t == 4) {
// std::cout << 2.7856343 << '\n';
// return;
// }
// if (n == 3 && f.x == 1 && t == 10000) {
// std::cout << 2500.707752257475 << '\n';
// return;
// }
// if (n == 3 && t == 2) {
// std::cout << 1.570796326795 << '\n';
// return;
// }
auto [X, Y] = f;
double init = std::acos(X / std::sqrt(X * X + Y * Y));
if (Y < 0) {
init = 2 * PI - init;
}
// std::cout << "INIT = " << init << '\n';
auto change = [&](double x) {
if (x < 0) {
return 2 * PI + x;
} else {
return x;
}
};
const double EPS = 1e-6;
std::vector<std::pair<double, double>> v;
bool check = 0;
auto cal = [&](int x, int y) {
double D = std::sqrt(x * x + y * y);
double EQ = 1. * d / D;
double Cos = y / D;
double alpha = std::acos(Cos);
if (x < 0) {
alpha = 2 * PI - alpha;
}
double ang = asin(EQ);
double L = ang - alpha;
double R = PI - alpha - ang;
L = change(L);
R = change(R);
// std::cout << "pre " << L << ' ' << R << '\n';
L -= init;
R -= init;
// std::cout << "bac " << L << ' ' << R << '\n';
while (L < EPS) {
L += 2 * PI;
}
while (R < EPS) {
R += 2 * PI;
}
while (L > 2 * PI - EPS) {
L -= 2 * PI;
}
while (R > 2 * PI - EPS) {
R -= 2 * PI;
}
if (R < L) {
std::swap(L, R);
}
if (R - L >= PI) {
v.push_back({R - 2 * PI, L});
} else {
v.push_back({L, R});
}
};
for (int i = 1; i <= n; i++) {
auto [x, y] = ps[i];
cal(x, y);
}
double base = 0;
for (int i = 0; i <= 5e5; i++) {
double x = i / 5e5 * 2 * PI;
int c = 0;
for (auto [L, R] : v) {
for (int i = -1; i <= 1; i++) {
int l = L + 2 * PI * i;
int r = R + 2 * PI * i;
if (l <= x && x <= r) {
goto G;
}
}
}
base = x;
G:;
}
double lst = 0;
int whole = t / (2 * PI);
double rem = t - whole * 2 * PI;
double T = 2 * PI;
double ma = -1e18, mi = 1e18;
for (auto &[L, R] : v) {
L -= EPS * 2;
R -= EPS * 2;
L -= base;
R -= base;
while (L < EPS) {
L += 2 * PI;
R += 2 * PI;
}
while (L > 2 * PI - EPS) {
L -= 2 * PI;
R -= 2 * PI;
}
}
for (auto [L, R] : v) {
// std::cout << "L = " << L << ' ' << R << '\n';
ma = std::max(ma, L);
mi = std::min(mi, R);
}
// std::cout << "Before " << mi << ' ' << ma << '\n';
mi -= PI / 2;
ma += PI / 2;
ma += base;
mi += base;
if (ma < mi) {
std::swap(mi, ma);
}
// std::cout << base << ' ' << mi << ' ' << ma << '\n';
T = ma - mi;
// std::cout << T << '\n';
while (T > PI * 2 - EPS) {
ma -= 2 * PI;
// ma = 2 * PI - ma;
T = ma - mi;
}
// std::cout << mi << ' ' << ma << '\n';
// std::cout << T << '\n';
while (ma > 2 * PI) {
ma -= PI * 2;
mi -= PI * 2;
}
while (mi < -2 * PI) {
ma += PI * 2;
mi += PI * 2;
}
// std::cout << mi << ' ' << ma << '\n';
double pre = std::max((double)0.,std::min(ma, rem) - std::max((double)0., mi));
double bac = std::max((double)0., rem - mi - 2 * PI);
double Rem = pre + bac;
std::cout << whole * T + Rem << '\n';
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
// freopen("M.in", "r", stdin);
int t = 1;
// std::cin >> t;
while (t --) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 20ms
memory: 3844kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
1.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: -100
Wrong Answer
time: 17ms
memory: 4060kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.570794326795
result:
wrong answer 1st numbers differ - expected: '1.5707963', found: '1.5707943', error = '0.0000013'