QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#468133 | #7846. Glacier Travel | lonelywolf | TL | 0ms | 4048kb | C++23 | 2.5kb | 2024-07-08 19:28:55 | 2024-07-08 19:28:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using db = double;
constexpr db eps = 1e-6;
int cmp(db a, db b) {
if (a - b > eps) {
return 1;
}
if (a - b < -eps) {
return -1;
}
return 0;
}
struct Point {
db x, y;
Point operator+(const Point& a) {
return {x + a.x, y + a.y};
}
Point operator-(const Point& a) {
return {x - a.x, y - a.y};
}
Point operator*(const db& a) {
return {x * a, y * a};
}
Point operator/(const db& a) {
return {x / a, y / a};
}
db len2() {
return x * x + y * y;
}
db len() {
return sqrt(len2());
}
Point unit() {
return (*this) / len();
}
};
db dis(Point a, Point b) {
return (b - a).len();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(10);
db s;
int n;
cin >> s >> n;
vector<Point> A(n);
for (auto &[x, y] : A) {
cin >> x >> y;
}
vector<db> sum(n);
vector<db> tim;
for (int i = 0; i < n - 1; i++) {
sum[i + 1] = sum[i] + dis(A[i], A[i + 1]);
}
for (int i = 0; i < n; i++) {
if (cmp(sum[i] + s, sum[n - 1]) <= 0) {
tim.push_back(sum[i]);
}
if (cmp(sum[i], s) >= 0) {
tim.push_back(sum[i] - s);
}
}
sort(tim.begin(), tim.end());
Point dir1, dir2;
int i1 = 0, i2 = 0;
db ans = 1e18;
for (int i = 0; i < tim.size() - 1; i++) {
db t1 = tim[i], t2 = tim[i + 1];
if (cmp(t1, t2) == 0) {
continue;
}
int l = -1, r = n;
while (l + 1 != r) {
int m = (l + r) / 2;
if (cmp(sum[m], t1) <= 0) {
l = m;
} else {
r = m;
}
}
i1 = l;
l = -1, r = n;
while (l + 1 != r) {
int m = (l + r) / 2;
if (cmp(sum[m], t1 + s) <= 0) {
l = m;
} else {
r = m;
}
}
i2 = l;
// while (i1 + 1 < n && cmp(sum[i1 + 1], t1) <= 0) {
// i1++;
// }
// while (i2 + 1 < n && cmp(sum[i2 + 1], t1 + s) <= 0) {
// i2++;
// }
dir1 = (A[i1 + 1] - A[i1]).unit();
dir2 = (A[i2 + 1] - A[i2]).unit();
auto calc = [&](db t) {
Point a = A[i1] + dir1 * (t - sum[i1]);
Point b = A[i2] + dir2 * (t + s - sum[i2]);
return dis(a, b);
};
while (t2 - t1 > eps) {
db lm = (2 * t1 + t2) / 3;
db rm = (t1 + 2 * t2) / 3;
if (calc(lm) > calc(rm)) {
t1 = lm;
} else {
t2 = rm;
}
}
ans = min(ans, calc(t1));
}
cout << ans << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4048kb
input:
5 4 20 0 10 0 10 10 0 10
output:
3.5355339059
result:
ok found '3.53553', expected '3.53553', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
3.16227766 9 -2 4 2 4 3 1 4 4 5 1 6 4 10 2 6 1 7 4
output:
0.9999999999
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
20 5 9 38 36 16 -5 36 -24 15 30 37
output:
2.2935957604
result:
ok found '2.29360', expected '2.29360', error '0.00000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
10 40 17 18 12 -5 12 -16 -10 16 7 -15 18 -18 19 15 -19 1 -18 11 -8 -12 -17 -12 5 -12 -15 -8 -10 -10 -4 4 -2 -3 15 17 -2 -9 -13 7 -12 17 15 -3 -19 -14 6 6 14 -5 -10 -15 17 -16 -11 15 9 -6 10 8 19 -1 12 -6 -18 2 14 17 9 -7 -8 -3 7 11 -12 -14 -19 4 -1 15 -17 16
output:
0.0000007794
result:
ok found '0.00000', expected '0.00000', error '0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
10 40 10 11 11 15 6 -16 -18 4 10 10 -10 16 -17 11 2 6 -6 -9 17 -7 -7 -5 10 -18 -9 9 -14 10 19 -3 -14 -3 15 -5 -3 16 -10 14 -9 -12 10 -18 10 -4 -9 -11 11 -2 9 2 12 15 2 -17 -8 -16 19 7 -19 -2 -17 7 16 -9 6 -6 8 -18 15 9 17 2 -19 12 -15 -9 1 -15 19 -12
output:
0.3442144373
result:
ok found '0.34421', expected '0.34421', error '0.00000'
Test #6:
score: -100
Time Limit Exceeded
input:
1000 4000 -720538 -681604 667325 347504 -911397 -962007 -264075 -858319 49605 149209 964851 361021 -397274 28661 -460607 -273701 104862 -136807 -803899 -693703 -974 -337735 323678 -209811 -745617 -358684 -984333 603546 722843 -444579 701511 -255784 -676477 -836480 998942 -227888 -502059 -438394 9641...