QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#617226#7846. Glacier TraveldreamwaveAC ✓17ms3992kbC++144.8kb2024-10-06 14:30:572024-10-06 14:30:58

Judging History

你现在查看的是最新测评结果

  • [2024-10-06 14:30:58]
  • 评测
  • 测评结果:AC
  • 用时:17ms
  • 内存:3992kb
  • [2024-10-06 14:30:57]
  • 提交

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'