QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#617226 | #7846. Glacier Travel | dreamwave | AC ✓ | 17ms | 3992kb | C++14 | 4.8kb | 2024-10-06 14:30:57 | 2024-10-06 14:30:58 |
Judging History
answer
#include <bits/stdc++.h>
#define double long double
using i64 = long long;
const int N = 2e6 + 10;
double s;
int n;
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
} ;
typedef Point Vector;
inline Vector operator + (Vector A, Vector B) {
return Vector(A.x + B.x, A.y + B.y);
}
inline Vector operator - (Vector A, Vector B) {
return Vector(A.x - B.x, A.y - B.y);
}
inline Vector operator * (Vector A, double p) {
return Vector(A.x * p, A.y * p);
}
inline Vector operator / (Vector A, double p) {
return Vector(A.x / p, A.y / p);
}
inline bool operator < (const Point &a, const Point &b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
const double eps = 1e-8;
inline int sgn(double x) {
if(fabs(x) < eps) return 0;
if(x < 0) return -1;
return 1;
}
inline int dcmp(double x, double y) {
if(fabs(x - y) < eps) return 0;
if(x > y) return 1;
return -1;
}
inline bool operator == (const Point &a, const Point &b) {
if(sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0) return 1;
return 0;
}
inline double Dot(Vector A, Vector B) { //点乘
return A.x * B.x + A.y * B.y;
}
inline double Length(Vector A) { //模长
return sqrt(Dot(A, A));
}
inline double Angle(Vector A, Vector B) { // 向量角
return acos(Dot(A, B) / Length(A) / Length(B));
}
inline double Cross(Vector A, Vector B) {//叉积
return A.x * B.y - A.y * B.x;
}
inline double Area2(Point A, Point B, Point C) {//有向平行四边形的面积
return Cross(B - A, C - A);
}
inline Vector Rotate(Vector A, double rad) { //逆时针旋转rad弧度后的向量
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
inline Vector Normal(Vector A) { //向量A左转90度的单位法向量
double L = Length(A);
return Vector(-A.y / L, A.x / L);
}
inline bool ToLeftTest(Point a, Point b, Point c) { //判断bc是不是ab的左转向
return Cross(b - a, c - b);
}
inline double ss(double s) {
return s * s;
}
void solve() {
std::cin >> s >> n;
std::vector < Point > p(n);
for(int i = 0; i < n; ++i) std::cin >> p[i].x >> p[i].y;
Point A = p[0], B = p[0];
int toA = 1, toB = 1;
double sts = 0;
while(1) {
double len = Length(p[toB] - B);
if(sts + len > s + eps) {
Vector used = p[toB] - B;
B = B + used * ((s - sts) / len);
break;
} else {
sts += len;
B = p[toB++];
}
}
auto f = [&](Point A, Point B, Vector k0, Vector k1) -> double {
A = A + k0;
B = B + k1;
return Length(B - A);
} ;
double ans = 1e18;
while(toB < n) {
double len1 = Length(p[toA] - A);
double len2 = Length(p[toB] - B);
// std::cerr << toA << ' ' << toB << '\n';
// std::cerr << A.x << ' ' << A.y << '\n';
// std::cerr << B.x << ' ' << B.y << '\n';
// std::cerr << len1 << ' ' << len2 << '\n';
Vector k1 = p[toA] - A;
Vector k2 = p[toB] - B;
if(dcmp(len1, len2) == 0) {
double l = 0, r = len1;
while(l + eps < r) {
double x = (2 * l + r) / 3;
double y = (2 * r + l) / 3;
if(f(A, B, k1 * (x / len1), k2 * (x / len1)) < f(A, B, k1 * (y / len1), k2 * (y / len1))) r = y;
else l = x;
}
ans = std::min(ans, f(A, B, k1 * (l / len1), k2 * (l / len2)));
A = p[toA++];
B = p[toB++];
} else if(dcmp(len1, len2) == 1) {
double l = 0, r = len2;
while(l + eps < r) {
double x = (2 * l + r) / 3;
double y = (2 * r + l) / 3;
if(f(A, B, k1 * (x / len1), k2 * (x / len2)) < f(A, B, k1 * (y / len1), k2 * (y / len2))) r = y;
else l = x;
}
ans = std::min(ans, f(A, B, k1 * (l / len1), k2 * (l / len2)));
B = p[toB++];
A = A + k1 * (len2 / len1);
} else {
double l = 0, r = len1;
while(l + eps < r) {
double x = (2 * l + r) / 3;
double y = (2 * r + l) / 3;
if(f(A, B, k1 * (x / len1), k2 * (x / len2)) < f(A, B, k1 * (y / len1), k2 * (y / len2))) r = y;
else l = x;
}
ans = std::min(ans, f(A, B, k1 * (l / len1), k2 * (l / len2)));
A = p[toA++];
B = B + k2 * (len1 / len2);
}
}
std::cout << ans << '\n';
}
int main() {
std::cin.tie(nullptr) -> sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(6);
int T = 1;
// std::cin >> T;
while(T--) solve();
return 0;
}///asdasd
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
input:
5 4 20 0 10 0 10 10 0 10
output:
3.535534
result:
ok found '3.53553', expected '3.53553', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
3.16227766 9 -2 4 2 4 3 1 4 4 5 1 6 4 10 2 6 1 7 4
output:
1.000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
20 5 9 38 36 16 -5 36 -24 15 30 37
output:
2.293596
result:
ok found '2.29360', expected '2.29360', error '0.00000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3804kb
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.000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3872kb
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.344214
result:
ok found '0.34421', expected '0.34421', error '0.00000'
Test #6:
score: 0
Accepted
time: 16ms
memory: 3972kb
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...
output:
0.044505
result:
ok found '0.04451', expected '0.04450', error '0.00000'
Test #7:
score: 0
Accepted
time: 17ms
memory: 3992kb
input:
1000 4000 703 909 500 496 -214 628 914 -44 -330 -238 -1424 -1426 347 1420 332 -1417 877 1678 -1390 819 -921 525 121 -923 -851 -859 512 -151 765 -109 416 -1529 -269 667 475 -234 -708 300 1917 -1935 -909 1342 1141 -696 -272 1295 1908 -1124 -898 -1225 1608 630 -1937 1246 -255 1021 -1005 -1650 -1595 -39...
output:
0.038186
result:
ok found '0.03819', expected '0.03819', error '0.00000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
40 3 100 0 0 100 0 0
output:
15.307337
result:
ok found '15.30734', expected '15.30734', error '0.00000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
48.2842712475 4 -10 -10 10 10 -10 10 10 -10
output:
0.000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'