QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497601#7670. MessengerMax_s_xaMAC ✓83ms17368kbC++144.8kb2024-07-29 14:43:302024-07-29 14:43:31

Judging History

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

  • [2024-07-29 14:43:31]
  • 评测
  • 测评结果:AC
  • 用时:83ms
  • 内存:17368kb
  • [2024-07-29 14:43:30]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 1e5 + 10;
const lf eps = 1e-8;

int n, m;

struct Point
{
    lf x, y;
    Point(lf _x = 0, lf _y = 0) : x(_x), y(_y) {}
    Point operator + (const Point &u) const { return Point(x + u.x, y + u.y); }
    Point operator - (const Point &u) const { return Point(x - u.x, y - u.y); }
    Point operator * (const lf &u) const { return Point(x * u, y * u); }
    Point operator / (const lf &u) const { return Point(x / u, y / u); }
};
inline lf sqr(const lf &x) { return x * x; }
inline lf dist(const Point &u) { return sqrt(sqr(u.x) + sqr(u.y)); }
inline lf dot(const Point &u, const Point &v) { return u.x * v.x + u.y * v.y; }
inline lf det(const Point &u, const Point &v) { return u.x * v.y - u.y * v.x; }
inline lf dist(const Point &x, const Point &y, const Point &u)
{
    lf ans = min(dist(x - u), dist(y - u));
    lf Dot = dot(u - x, y - x), d2 = dist(y - x);
    if (Dot > 0 && Dot < d2 * d2) ans = min(ans, abs(det(y - x, u - x)) / d2);
    return ans;
}

Point a[MAXN], b[MAXN], ia[MAXN], ib[MAXN];
Point c[MAXN], ic[MAXN];
lf da[MAXN], db[MAXN], dc[MAXN];

inline bool Check(lf x)
{
    lf dt = 0; int tot = 0;
    for (int i = 2; i <= m; i++)
    {
        if (dt + db[i] <= x) { dt += db[i]; continue; }
        Point tmp = b[i - 1];
        b[i - 1] = b[i - 1] + ib[i] * (x - dt), db[i] -= x - dt;
        lf ta = 0, tb = 0;
        c[tot = 1] = b[i - 1] - a[1];
        for (int u = 2, v = i; u <= n && v <= m;)
            if (tb + db[v] < ta + da[u])
            {
                tot++, ic[tot] = (u > n ? ib[v] : ib[v] - ia[u]), dc[tot] = tb + db[v] - max(tb, ta), c[tot] = c[tot - 1] + ic[tot] * dc[tot];
                tb += db[v], v++;
            }
            else
            {
                tot++, ic[tot] = ib[v] - ia[u], dc[tot] = ta + da[u] - max(tb, ta), c[tot] = c[tot - 1] + ic[tot] * dc[tot];
                ta += da[u], u++;
            }
        b[i - 1] = tmp, db[i] += x - dt;
        break;
    }
    lf mn = 1e18;
    for (int i = 2; i <= tot; i++) mn = min(mn, dist(c[i - 1], c[i], Point(0, 0)));
    return mn < x || abs(mn - x) < eps;
}

int main()
{
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n);
    for (int i = 1; i <= n; i++) Read(a[i].x), Read(a[i].y);
    for (int i = 2; i <= n; i++) ia[i] = a[i] - a[i - 1], da[i] = dist(ia[i]), ia[i] = ia[i] / da[i];
    Read(m);
    for (int i = 1; i <= m; i++) Read(b[i].x), Read(b[i].y);
    lf sum = 0;
    for (int i = 2; i <= m; i++) ib[i] = b[i] - b[i - 1], db[i] = dist(ib[i]), ib[i] = ib[i] / db[i], sum += db[i];

    lf l = 0, r = sum, mid;
    if (dist(b[m] - a[1]) - sum > eps) return cout << "impossible\n", 0;
    while (r - l > eps)
    {
        mid = (l + r) / 2;
        if (Check(mid)) r = mid;
        else l = mid;
    }
    cout << fixed << setprecision(10) << l << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 16212kb

input:

2
0 0
0 10
2
4 10
4 0

output:

3.9999999851

result:

ok correct

Test #2:

score: 0
Accepted
time: 2ms
memory: 14212kb

input:

2
0 0
1 0
3
2 0
3 0
3 10

output:

4.9999999492

result:

ok correct

Test #3:

score: 0
Accepted
time: 2ms
memory: 15952kb

input:

2
0 30000
0 0
2
0 0
30000 0

output:

impossible

result:

ok correct

Test #4:

score: 0
Accepted
time: 2ms
memory: 16216kb

input:

2
0 30000
0 0
2
30000 0
0 0

output:

0.0000000000

result:

ok correct

Test #5:

score: 0
Accepted
time: 1ms
memory: 13908kb

input:

2
30000 0
0 0
2
30000 30000
0 30000

output:

impossible

result:

ok correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 16072kb

input:

2
30000 0
0 0
2
0 30000
30000 30000

output:

29999.9999999864

result:

ok correct

Test #7:

score: 0
Accepted
time: 30ms
memory: 16616kb

input:

50000
0 0
1 0
1 1
2 1
2 2
3 2
3 3
4 3
4 4
5 4
5 5
6 5
6 6
7 6
7 7
8 7
8 8
9 8
9 9
10 9
10 10
11 10
11 11
12 11
12 12
13 12
13 13
14 13
14 14
15 14
15 15
16 15
16 16
17 16
17 17
18 17
18 18
19 18
19 19
20 19
20 20
21 20
21 21
22 21
22 22
23 22
23 23
24 23
24 24
25 24
25 25
26 25
26 26
27 26
27 27
28 ...

output:

3.3137084909

result:

ok correct

Test #8:

score: 0
Accepted
time: 2ms
memory: 14176kb

input:

2
0 0
30000 30000
2
0 30000
30000 0

output:

0.0000000000

result:

ok correct

Test #9:

score: 0
Accepted
time: 1ms
memory: 13968kb

input:

2
0 30000
0 0
2
1 0
0 0

output:

impossible

result:

ok correct

Test #10:

score: 0
Accepted
time: 2ms
memory: 16204kb

input:

2
0 1
0 0
2
30000 0
0 0

output:

14999.4999999944

result:

ok correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 16252kb

input:

2
0 0
15000 0
2
30000 0
15000 0

output:

0.0000000000

result:

ok correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 16200kb

input:

2
0 0
14999 0
2
30000 0
15000 0

output:

0.9999999907

result:

ok correct

Test #13:

score: 0
Accepted
time: 2ms
memory: 15956kb

input:

2
0 0
15000 0
2
30000 0
15001 0

output:

impossible

result:

ok correct

Test #14:

score: 0
Accepted
time: 1ms
memory: 14168kb

input:

2
0 15000
0 0
2
0 15000
0 30000

output:

0.0000000000

result:

ok correct

Test #15:

score: 0
Accepted
time: 2ms
memory: 16036kb

input:

2
0 14999
0 0
2
0 15000
0 30000

output:

impossible

result:

ok correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 16212kb

input:

2
0 0
0 30000
2
0 30000
0 0

output:

0.0000000000

result:

ok correct

Test #17:

score: 0
Accepted
time: 0ms
memory: 15872kb

input:

2
0 30000
0 15000
2
0 15000
0 0

output:

impossible

result:

ok correct

Test #18:

score: 0
Accepted
time: 2ms
memory: 16008kb

input:

2
0 0
30000 30000
2
1 1
30000 30000

output:

impossible

result:

ok correct

Test #19:

score: 0
Accepted
time: 2ms
memory: 16216kb

input:

3
0 30000
15000 15000
0 0
3
30000 30000
15000 15000
30000 0

output:

0.0000000000

result:

ok correct

Test #20:

score: 0
Accepted
time: 2ms
memory: 16024kb

input:

2
0 0
0 1
3
30000 12426
30000 0
30000 30000

output:

impossible

result:

ok correct

Test #21:

score: 0
Accepted
time: 2ms
memory: 16256kb

input:

2
0 0
0 1
3
30000 12427
30000 0
30000 30000

output:

42424.9750140449

result:

ok correct

Test #22:

score: 0
Accepted
time: 2ms
memory: 16076kb

input:

4
0 30000
0 0
1 0
1 30000
4
30000 30000
30000 0
29999 0
29999 30000

output:

29998.9999999835

result:

ok correct

Test #23:

score: 0
Accepted
time: 19ms
memory: 17012kb

input:

50000
0 0
1 0
1 1
2 1
2 2
3 2
3 3
4 3
4 4
5 4
5 5
6 5
6 6
7 6
7 7
8 7
8 8
9 8
9 9
10 9
10 10
11 10
11 11
12 11
12 12
13 12
13 13
14 13
14 14
15 14
15 15
16 15
16 16
17 16
17 17
18 17
18 18
19 18
19 19
20 19
20 20
21 20
21 21
22 21
22 22
23 22
23 23
24 23
24 24
25 24
25 25
26 25
26 26
27 26
27 27
28 ...

output:

24142.1356236960

result:

ok correct

Test #24:

score: 0
Accepted
time: 35ms
memory: 16660kb

input:

50000
0 0
1 0
1 1
2 1
2 2
3 2
3 3
4 3
4 4
5 4
5 5
6 5
6 6
7 6
7 7
8 7
8 8
9 8
9 9
10 9
10 10
11 10
11 11
12 11
12 12
13 12
13 13
14 13
14 14
15 14
15 15
16 15
16 16
17 16
17 17
18 17
18 18
19 18
19 19
20 19
20 20
21 20
21 21
22 21
22 22
23 22
23 23
24 23
24 24
25 24
25 25
26 25
26 26
27 26
27 27
28 ...

output:

0.0000000000

result:

ok correct

Test #25:

score: 0
Accepted
time: 0ms
memory: 14164kb

input:

2
1 10
1 11
5
3 8
2 9
10 2
10 3
8 8

output:

1.4142135526

result:

ok correct

Test #26:

score: 0
Accepted
time: 0ms
memory: 16216kb

input:

3
5 0
0 6
3 6
9
0 2
6 8
6 5
2 5
2 2
9 4
5 0
7 0
8 10

output:

1.9735690884

result:

ok correct

Test #27:

score: 0
Accepted
time: 2ms
memory: 16212kb

input:

8
4487 25213
15925 2555
11834 19731
24882 25400
29873 18185
20332 1130
20912 4660
2260 17776
7
1181 9778
6861 17903
1110 10850
8648 15950
13243 28850
23075 19352
14768 3464

output:

1452.5639082177

result:

ok correct

Test #28:

score: 0
Accepted
time: 1ms
memory: 14164kb

input:

8
5171 18241
3918 24817
6039 21929
19392 10844
5465 21271
18464 27403
5672 17224
17352 23648
8
13743 27832
6508 18183
93 25279
429 836
959 12741
1631 9065
17093 3127
6232 13449

output:

2339.7594870052

result:

ok correct

Test #29:

score: 0
Accepted
time: 0ms
memory: 16148kb

input:

306
7 0
1 4
9 7
8 6
3 7
2 5
9 2
5 8
6 2
4 9
5 10
10 10
10 3
5 1
3 8
9 6
7 4
8 9
6 4
10 6
6 8
6 3
10 1
0 7
8 5
2 4
1 10
10 10
4 10
10 3
1 10
7 5
1 2
10 8
1 2
3 7
6 1
6 8
5 3
2 8
7 2
0 6
2 5
7 3
0 9
2 9
7 9
8 7
7 1
1 5
7 8
9 3
9 9
0 2
6 7
7 5
5 9
8 4
7 7
8 6
8 0
0 3
0 10
3 6
6 3
1 7
8 5
3 9
7 9
2 7
3 ...

output:

0.0104863221

result:

ok correct

Test #30:

score: 0
Accepted
time: 0ms
memory: 16136kb

input:

283
10 2
8 8
2 9
5 3
6 7
6 2
3 3
10 9
10 4
9 7
3 3
9 6
3 10
3 0
6 10
1 7
8 3
0 5
3 8
10 0
9 4
7 3
3 6
3 2
10 5
6 2
3 6
8 3
10 8
2 6
3 4
2 10
2 8
7 10
0 5
5 0
6 6
2 6
8 9
10 3
6 3
3 9
8 10
0 7
0 10
0 8
1 8
7 1
0 1
7 10
0 1
1 9
8 3
5 10
9 6
7 5
9 8
5 8
8 6
3 5
9 1
9 8
6 1
6 0
0 0
8 1
1 10
2 0
5 0
3 1
...

output:

0.0000000000

result:

ok correct

Test #31:

score: 0
Accepted
time: 2ms
memory: 16212kb

input:

99
246 227
1374 887
973 515
505 835
445 502
1524 361
589 217
728 637
988 74
1312 1493
192 485
150 951
903 1575
1358 1114
1564 829
262 1465
922 1078
679 912
561 947
1321 1165
948 1333
684 1456
243 1470
654 1373
894 897
149 1089
424 1162
213 293
845 555
508 441
999 1549
406 1020
16 1437
1335 112
174 1...

output:

18.2276316982

result:

ok correct

Test #32:

score: 0
Accepted
time: 2ms
memory: 14140kb

input:

625
189 776
733 112
1550 794
1148 1341
1236 403
944 153
1152 459
1271 831
203 358
912 1530
1196 1401
1014 758
378 736
130 182
555 20
1425 200
587 755
606 666
1423 1451
624 423
110 1403
26 424
1437 956
796 961
602 1586
331 373
850 800
1559 1508
536 1494
3 598
906 551
1162 1231
1348 106
592 1255
694 1...

output:

4.2479691555

result:

ok correct

Test #33:

score: 0
Accepted
time: 27ms
memory: 16460kb

input:

18051
32 15
3 3
11 2
2 30
32 14
15 25
34 16
10 12
13 31
14 16
15 35
16 24
18 35
24 4
11 22
21 7
24 12
6 32
25 24
23 2
21 2
3 15
13 9
32 6
26 25
21 30
20 23
22 5
16 11
26 15
15 27
25 32
31 28
5 19
15 20
1 25
3 24
30 5
29 11
19 11
26 9
9 29
7 1
15 3
35 32
18 4
13 25
23 25
32 11
10 19
25 0
28 6
5 35
13...

output:

0.0000000000

result:

ok correct

Test #34:

score: 0
Accepted
time: 4ms
memory: 16228kb

input:

1587
1 16
34 21
28 4
16 22
35 8
1 15
20 18
10 15
23 16
1 23
16 14
15 22
3 34
4 35
34 22
32 16
19 20
7 10
13 20
16 8
11 26
24 35
25 26
19 14
21 4
10 11
3 30
15 11
21 12
11 0
25 17
1 0
33 31
2 26
14 21
19 1
0 32
19 19
3 5
30 29
5 18
21 29
28 8
34 2
25 22
14 5
32 7
1 21
13 23
8 35
31 26
9 2
2 24
25 23
...

output:

0.0144415697

result:

ok correct

Test #35:

score: 0
Accepted
time: 79ms
memory: 16396kb

input:

50000
13 5
18 3
8 23
18 33
27 15
14 27
19 22
32 10
18 32
4 35
19 3
17 12
15 33
7 6
30 19
29 8
23 26
1 16
28 25
19 31
21 9
32 11
8 30
7 16
18 18
11 12
30 9
21 35
4 35
2 5
16 21
24 25
10 7
35 24
21 10
5 30
8 0
22 15
19 0
0 33
29 8
31 6
25 29
22 16
22 24
28 25
22 13
28 22
0 29
27 11
0 12
0 1
24 22
19 1...

output:

0.0000000000

result:

ok correct

Test #36:

score: 0
Accepted
time: 83ms
memory: 17368kb

input:

50000
19 16
34 16
26 17
19 6
30 25
11 13
23 13
26 30
22 5
29 19
0 33
29 15
32 23
7 34
28 27
29 23
34 31
33 14
26 10
23 34
21 35
16 0
0 26
2 2
9 25
2 4
17 9
8 1
4 27
7 5
28 14
24 3
24 18
6 22
35 33
10 0
30 20
8 7
11 12
14 21
8 14
1 14
27 24
5 29
2 14
10 19
20 24
13 31
28 32
18 19
29 14
22 34
34 5
1 2...

output:

0.0000000000

result:

ok correct

Test #37:

score: 0
Accepted
time: 0ms
memory: 16212kb

input:

4
5 5
5 2
4 5
7 6
50000
30 27
31 3
22 30
38 31
39 13
29 33
41 28
21 5
50 26
29 6
42 17
37 12
41 29
35 11
38 30
39 9
45 0
32 7
44 31
40 0
44 30
31 11
31 24
37 4
42 15
23 16
35 28
23 27
25 27
30 35
25 25
44 29
39 12
42 32
44 27
22 22
47 34
22 8
23 14
32 6
39 12
32 25
34 21
29 4
41 35
28 3
40 9
43 19
4...

output:

22.0379614556

result:

ok correct

Test #38:

score: 0
Accepted
time: 3ms
memory: 16204kb

input:

9
4 10
4 1
8 6
7 4
0 5
4 9
10 1
1 2
1 4
50000
48 7
40 0
42 29
22 13
46 19
35 21
40 19
54 15
55 26
36 21
44 16
31 30
20 5
37 31
51 9
45 31
26 15
54 30
51 1
54 2
54 22
31 2
52 19
43 17
26 31
41 20
38 20
39 19
44 34
52 1
33 29
33 11
38 28
30 29
43 20
52 8
36 29
26 20
45 23
39 13
53 5
47 10
52 3
54 7
40...

output:

20.2431066010

result:

ok correct

Test #39:

score: 0
Accepted
time: 2ms
memory: 14544kb

input:

2
4 19317
4 19318
37985
41 27
37 16
47 27
31 15
36 13
24 20
49 25
51 23
49 1
33 16
27 16
53 29
43 17
40 9
20 21
24 3
21 19
44 10
36 20
55 15
30 30
35 32
33 26
26 5
35 29
47 27
50 20
33 31
33 3
34 8
35 20
32 23
34 30
26 17
29 10
36 34
21 25
54 29
40 7
38 17
39 9
46 20
35 30
31 33
20 8
32 30
33 26
37 ...

output:

19289.9111706126

result:

ok correct

Test #40:

score: 0
Accepted
time: 3ms
memory: 16532kb

input:

6
3 25333
0 26159
6 15490
0 3432
4 8641
0 15506
41088
40 9
24 34
30 18
25 25
44 10
55 12
24 14
25 1
21 21
28 16
33 26
42 32
31 34
41 20
50 25
46 4
27 4
23 29
48 8
39 18
54 3
38 14
31 30
55 24
41 2
31 16
45 18
40 32
24 31
39 31
31 2
39 2
26 29
37 22
53 11
29 21
31 31
47 7
35 18
33 4
29 4
28 27
49 14
...

output:

3406.3776154870

result:

ok correct

Test #41:

score: 0
Accepted
time: 0ms
memory: 14124kb

input:

4
7 18240
5 26771
3 24943
0 6628
7
20 1906
27 15217
20 15532
21 11073
27 334
23 16131
23 18367

output:

3222.0933119255

result:

ok correct

Test #42:

score: 0
Accepted
time: 2ms
memory: 16260kb

input:

4
8 15367
9 13231
10 3412
5 16414
10
26 15046
22 22728
24 22149
20 7329
27 26701
22 4714
27 4268
27 13007
28 27715
20 13727

output:

13.8607797362

result:

ok correct

Test #43:

score: 0
Accepted
time: 2ms
memory: 16164kb

input:

8
15009 21979
15010 23864
15007 5225
15003 4757
15009 16970
15007 15279
15003 4170
15007 27635
864
14373 15544
14972 14279
14674 14827
14729 14520
15657 15248
14953 14950
14346 14312
14476 14874
14476 15320
15384 15757
15017 15028
14567 14633
15610 14904
14751 15493
14357 14490
15321 14795
14676 151...

output:

17.8897882606

result:

ok correct

Test #44:

score: 0
Accepted
time: 1ms
memory: 14124kb

input:

6
15005 29323
15004 1778
15008 23555
15000 19170
15010 25875
15010 15988
154
15757 14866
15689 15407
14776 15688
15444 15769
15627 14793
14834 15211
14211 14961
14905 15228
14634 14324
15317 14937
15402 15641
15290 14306
14925 14641
14936 14261
15472 14801
15124 15800
14660 15632
15311 15017
15074 1...

output:

0.5386713568

result:

ok correct

Test #45:

score: 0
Accepted
time: 57ms
memory: 16896kb

input:

50000
30 20
9 34
25 8
24 4
35 34
6 29
9 15
25 7
4 1
26 21
8 5
31 33
11 28
16 23
29 10
1 30
15 23
14 4
19 22
7 27
11 9
20 12
11 23
30 16
29 24
15 3
5 19
3 2
27 18
25 23
9 2
2 22
18 25
34 35
31 0
35 10
26 28
33 13
28 0
30 33
18 28
0 19
7 25
31 23
26 6
31 33
4 33
5 12
25 15
2 18
22 19
19 5
13 24
13 6
1...

output:

42332.4154625816

result:

ok correct

Test #46:

score: 0
Accepted
time: 57ms
memory: 16336kb

input:

50000
31 13
2 25
10 20
1 31
9 33
9 28
0 32
30 20
18 15
30 34
10 20
6 1
34 14
26 21
19 18
20 27
11 34
12 18
29 32
8 26
34 10
12 16
15 35
33 30
23 19
26 7
32 12
6 10
27 33
14 11
23 8
6 7
15 10
1 32
16 17
31 26
8 8
11 23
10 34
6 15
7 29
2 16
6 35
17 14
5 8
28 2
6 12
32 7
30 27
6 23
15 27
20 30
17 2
31 ...

output:

42333.5614531233

result:

ok correct