QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#737910 | #7027. Machining Disc Rotors | SGColin# | TL | 1ms | 4176kb | C++17 | 2.2kb | 2024-11-12 17:08:45 | 2024-11-12 17:08:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
inline ll rd() {
ll x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
const ld PI = 3.1415926535897932384;
const ld a90 = atan(1) * 2;
const ld a180 = a90 * 2, a270 = a90 * 3, a360 = a90 * 4;
const ld dlt[2][2] = {0, a180, a360, a180};
inline ld angle(ld x, ld y) { // counterclockwise, start from (1, 0)
if (fabs(x) < 1e-15) return a90 * (1 + 2 * (y < 0));
else return atan(y / x) + dlt[y < 0][x < 0];
}
int testcase = 0;
inline void work() {
int n = rd();
ld R = rd();
ld R2 = R * R;
vector<pair<ld, ld>> s;
rep(i, 1, n) {
ld x = rd(), y = rd(), rr = rd();
ld theta0 = angle(x, y);
ld rho02 = x * x + y * y;
ld rho0 = sqrt(rho02);
ld dlt = acos((rho02 + R2 - rr * rr) / (2 * rho0 * R));
ld l = theta0 - dlt;
ld r = theta0 + dlt;
if (r > 2 * PI) {
r -= 2 * PI;
l -= 2 * PI;
}
if (l < 0) {
s.eb(l + 2 * PI, 2 * PI);
s.eb(0, r);
} else s.eb(l, r);
}
vector<pair<ld, ld>> segs;
ld nw = 0;
sort(all(s));
for (auto [l, r] : s) {
if (nw != l) segs.eb(nw, l);
nw = r;
}
if (nw != 2 * PI) segs.eb(nw, 2 * PI);
auto calc = [&](ld ang) {
return sqrt(R2 * (2 - 2 * cos(ang)));
};
ld ans = 0;
for (auto [l1, r1] : segs)
for (auto [l2, r2] : segs) {
ld nwl = l1 - r2, nwr = r1 - l2;
ans = max(ans, calc(nwl));
ans = max(ans, calc(nwr));
if (nwl < -PI && -PI < nwr) ans = max(ans, 2 * R);
if (nwl < PI && PI < nwr) ans = max(ans, 2 * R);
}
printf("Case #%d: %.18lf\n", ++testcase, (double)ans);
}
int main() {
per(t, rd(), 1) work();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4176kb
input:
1 3 10 0 12 10 11 -6 10 -11 -6 10
output:
Case #1: 18.611654895000253163
result:
ok 1 cases
Test #2:
score: -100
Time Limit Exceeded
input:
5000 3 1000 750 500 625 -250 -625 625 -1000 1000 1000 3 8 -6 -4 5 2 5 5 8 -8 8 1 710 426 -568 994 1 10 -8 6 15 14 931 622 -651 207 -930 438 552 931 890 743 -264 -923 671 889 -315 179 15 761 173 -440 883 81 -938 -310 170 -271 981 91 918 -88 47 136 927 26 903 29 61 -162 936 22 917 129 18 32 595 431 11...
output:
Case #1: 1998.628237512162741041 Case #2: 15.989025900097303179 Case #3: 1420.000000000000000000 Case #4: 19.843134832984429039 Case #5: 1862.000000000000000000 Case #6: 1190.000000000000000000 Case #7: 934.000000000000000000 Case #8: 542.000000000000000000 Case #9: 1808.000000000000000000 Case #10:...