QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#801364#4769. Keeping the Dogs ApartLeGustoAC ✓144ms26820kbC++145.1kb2024-12-06 21:50:302024-12-06 21:50:31

Judging History

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

  • [2024-12-06 21:50:31]
  • 评测
  • 测评结果:AC
  • 用时:144ms
  • 内存:26820kb
  • [2024-12-06 21:50:30]
  • 提交

answer

#include <bits/stdc++.h>
using pdd = std::pair<long double, long double>;
using ll = long long;
long double EPS = 0.000001;

using namespace std;

struct Point {
    long double x;
    long double y;

    Point(long double a, long double b) {
        x = a;
        y = b;
    }
    Point() {

    }
};

struct Line {
    long double start_time = -1;
    long double end_time = -1;
    Point* p1 = nullptr;
    Point* p2 = nullptr;

    Line(Point* a, Point* b, long double c, long double d) {
        p1 = a;
        p2 = b;
        start_time = c;
        end_time = d;
        //cout<<start_time<<" "<<end_time<<" times\n";
    }
};

long double eucl_dist(Point* a, Point* b) {
    return sqrt((a->x - b->x)*(a->x - b->x) + (a->y - b->y)*(a->y - b->y));
}

pdd get_direction(Line* a) {
    return {(a->p2->x - a->p1->x) / eucl_dist(a->p1, a->p2), (a->p2->y - a->p1->y) / eucl_dist(a->p1, a->p2)};
}

/// find distance between point and line segment
long double calc_ans(pdd p1, pdd q1, pdd p) {
    //cout<<start_b.first<<" "<<start_b.second<<"heeee\n";
    pdd pp1 = {p.first-p1.first, p.second-p1.second};
    pdd q1p1 = {q1.first-p1.first, q1.second-p1.second};
    long double u = (pp1.first*q1p1.first + pp1.second*q1p1.second)/(q1p1.first*q1p1.first + q1p1.second*q1p1.second);
    pdd p_prime = {p1.first + u*q1p1.first, p1.second + u*q1p1.second};
    //cout<<u<<endl;
    if (u < EPS || u-1 > EPS) return 99999999;
    return sqrt((p.first-p_prime.first)*(p.first-p_prime.first) + (p.second-p_prime.second)*(p.second-p_prime.second));
}

long double calc_distance(Line* a, Line* b) {
    /// make sure a starts earlier

    if (a->start_time > b->start_time) swap(a, b);

    /// no overlap

    if (a->end_time - b->start_time <= EPS)  return 999999999;


    pdd direction_a = get_direction(a);
    pdd direction_b = get_direction(b);


    long double timer = min(a->end_time, b->end_time) - b->start_time;
    //cout<<timer<<" whar\n";



    /// positions of both dogs when dog b starts walking and their paths
    long double dif = b->start_time - a->start_time;


    //cout<<fixed<<setprecision(9)<<dif<<"\n";
    pdd start_a = {a->p1->x + dif * direction_a.first, a->p1->y + dif * direction_a.second };
    pdd start_b = {b->p1->x, b->p1->y};

    //cout<<start_a.first<<" "<<start_a.second<<" br\n";

    pdd delta_a = {direction_a.first * timer, direction_a.second * timer};
    pdd delta_b = {direction_b.first * timer, direction_b.second * timer};

    pdd end_a = {start_a.first + delta_a.first - delta_b.first, start_a.second + delta_a.second - delta_b.second};

    //cout<<"start_dist: "<<eucl_dist(new Point(start_b.first, start_b.second), new Point(start_a.first, start_a.second))<<" dist2: "<<
                           //eucl_dist(new Point(start_b.first, start_b.second), new Point(end_a.first, end_a.second))<<"\n";

    /// get minimum of distance from point to both ends of the line segment
    long double ans = min(eucl_dist(new Point(start_b.first, start_b.second), new Point(start_a.first, start_a.second)),
                           eucl_dist(new Point(start_b.first, start_b.second), new Point(end_a.first, end_a.second)));

    /// compare with shortest distance algorithm
    ans = min(ans, calc_ans(start_a, end_a, start_b));

    return ans;
}

vector<Line*> dog1;
vector<Line*> dog2;

int main() {
    /// read input for first dog path
    int n;
    cin>>n;
    Point* curr = new Point();
    cin>>curr->x>>curr->y;
    long double curr_time = 0;
    for (int i = 0; i<n-1; i++) {
        int x, y;
        cin>>x>>y;

        Point* next_point = new Point(x, y);
        long double start_t = curr_time;
        curr_time += eucl_dist(curr, next_point);
        long double end_t = curr_time;

        dog1.push_back(new Line(curr, next_point, start_t, end_t));
        curr = next_point;
    }

    /// read input for second dog path
    int m;
    cin>>m;

    Point* nc = new Point();
    cin>>nc->x>>nc->y;
    curr = nc;

    curr_time = 0;
    for (int i = 0; i<m-1; i++) {
        int x, y;
        cin>>x>>y;

         Point* next_point = new Point(x, y);
        long double start_t = curr_time;
        curr_time += eucl_dist(curr, next_point);
        long double end_t = curr_time;

        dog2.push_back(new Line(curr, next_point, start_t, end_t));
        curr = next_point;
    }

    /// two pointers on the dogs to keep track of path order
    int dog1_left = 0;
    int dog2_left = 0;
    long double ans = eucl_dist(dog1[0]->p1, dog2[0]->p1);


    while (dog1_left != dog1.size() && dog2_left != dog2.size()) {
            //cout<<ans<<"\n";
        Line* l1 = dog1[dog1_left];
        Line* l2 = dog2[dog2_left];
        long double calc = calc_distance(l1, l2);
        ans = min(ans, calc);
        if (l1->end_time < l2->end_time) dog1_left++;
        //if (l1->start_time < l2->start_time || (l1->start_time == l2->start_time && l1->end_time < l2->end_time)) dog1_left++;
        else dog2_left++;
    }

    cout<<fixed<<setprecision(9)<<ans<<"\n";
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
0 0
10 0
2
30 0
15 0

output:

10.000000000

result:

ok found '10.00000', expected '10.00000', error '0.00000'

Test #2:

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

input:

5
10 0
10 8
2 8
2 0
10 0
9
0 8
4 8
4 12
0 12
0 8
4 8
4 12
0 12
0 8

output:

1.414213562

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #3:

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

input:

8
0 0
0 4
5 4
7 8
12 3
14 8
6 5
1 1
8
5 3
5 7
10 7
12 11
17 6
19 11
11 8
6 4

output:

5.830951895

result:

ok found '5.83095', expected '5.83095', error '0.00000'

Test #4:

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

input:

8
0 0
0 4
5 4
7 8
12 3
14 8
6 5
1 1
11
5 3
5 7
10 7
12 11
17 6
19 11
11 8
6 4
3 2
1 2
0 1

output:

5.830951895

result:

ok found '5.83095', expected '5.83095', error '0.00000'

Test #5:

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

input:

4
4510 4603
4506 4590
4503 4585
4494 4597
4
4569 5398
4579 5411
4578 5398
4585 5387

output:

797.186301940

result:

ok found '797.18630', expected '797.18630', error '0.00000'

Test #6:

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

input:

5
4891 4526
4897 4525
4893 4528
4887 4518
4876 4530
7
5010 4733
5010 4743
5016 4754
5028 4748
5038 4739
5028 4737
5037 4735

output:

238.767669503

result:

ok found '238.76767', expected '238.76767', error '0.00000'

Test #7:

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

input:

8
4785 4700
4789 4694
4781 4687
4788 4680
4780 4683
4782 4681
4776 4682
4775 4679
9
4864 5048
4856 5044
4863 5056
4872 5062
4862 5064
4864 5068
4858 5063
4855 5055
4864 5065

output:

356.854312010

result:

ok found '356.85431', expected '356.85431', error '0.00000'

Test #8:

score: 0
Accepted
time: 80ms
memory: 26820kb

input:

100000
5480 5389
5488 5392
5491 5405
5498 5416
5498 5420
5496 5425
5484 5415
5480 5422
5479 5428
5488 5424
5497 5421
5509 5424
5503 5416
5506 5427
5504 5439
5511 5446
5520 5434
5526 5422
5533 5431
5541 5419
5533 5419
5541 5417
5539 5426
5550 5437
5539 5443
5531 5434
5531 5438
5541 5448
5538 5449
554...

output:

203.972121715

result:

ok found '203.97212', expected '203.97212', error '0.00000'

Test #9:

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

input:

3
0 0
1 1
2 0
3
1 4
2 3
3 4

output:

2.236067977

result:

ok found '2.23607', expected '2.23607', error '0.00000'

Test #10:

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

input:

5
0 0
0 3
3 3
3 0
0 0
5
0 3
3 3
3 0
0 0
0 3

output:

2.121320344

result:

ok found '2.12132', expected '2.12132', error '0.00000'

Test #11:

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

input:

5
0 0
0 3
3 4
3 1
0 1
5
0 3
3 4
3 1
0 1
0 3

output:

1.754130854

result:

ok found '1.75413', expected '1.75413', error '0.00000'

Test #12:

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

input:

2
0 0
3 3
2
6 7
3 4

output:

1.000000000

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #13:

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

input:

2
3 3
0 0
2
3 4
6 7

output:

1.000000000

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #14:

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

input:

2
0 0
1000 1000
2
1000 0
0 1000

output:

0.000000000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #15:

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

input:

2
0 1
1 0
2
10000 9999
9999 10000

output:

14140.721410169

result:

ok found '14140.72141', expected '14140.72141', error '0.00000'

Test #16:

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

input:

2
1 0
1 10000
2
0 1
10000 0

output:

0.000070711

result:

ok found '0.00007', expected '0.00007', error '0.00000'

Test #17:

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

input:

2
0 0
1 1000
2
1 0
0 999

output:

0.000000500

result:

ok found '0.00000', expected '0.00000', error '0.00000'

Test #18:

score: 0
Accepted
time: 74ms
memory: 26704kb

input:

100000
0 1
10000 10000
0 2
9999 10000
0 3
9998 10000
0 4
9997 10000
0 5
9996 10000
0 6
9995 10000
0 7
9994 10000
0 8
9993 10000
0 9
9992 10000
0 10
9991 10000
0 11
9990 10000
0 12
9989 10000
0 13
9988 10000
0 14
9987 10000
0 15
9986 10000
0 16
9985 10000
0 17
9984 10000
0 18
10000 10000
0 19
9999 10...

output:

0.707142139

result:

ok found '0.70714', expected '0.70714', error '0.00000'

Test #19:

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

input:

100000
210 9951
3265 5372
4673 7680
2428 8939
2127 9083
3012 9215
1486 9881
2420 9794
1579 7893
4659 7434
3547 5440
4510 5779
4172 5776
1429 8820
4831 7267
2791 6931
433 8373
4541 8425
2044 8386
4822 6031
4797 7069
639 9174
2553 5801
2096 6271
1664 7955
2941 5884
3749 7231
982 9267
1639 9662
4150 75...

output:

2696.041215955

result:

ok found '2696.04122', expected '2696.04122', error '0.00000'

Test #20:

score: 0
Accepted
time: 144ms
memory: 26800kb

input:

100000
0 0
10000 0
10000 10000
0 10000
0 0
10000 0
10000 10000
0 10000
0 0
10000 0
10000 10000
0 10000
0 0
10000 0
10000 10000
0 10000
0 0
10000 0
10000 10000
0 10000
0 0
10000 0
10000 10000
0 10000
0 0
10000 0
10000 10000
0 10000
0 0
10000 0
10000 10000
0 10000
0 0
10000 0
10000 10000
0 10000
0 0
1...

output:

1.414213562

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #21:

score: 0
Accepted
time: 72ms
memory: 26664kb

input:

100000
3997 1457
8849 1992
9331 9942
7606 4506
9291 4865
2467 8754
2204 9362
9517 8240
5628 8319
119 6367
8020 1425
876 1849
3375 6490
6206 9258
6514 4973
754 4978
1197 75
392 1449
6993 7632
8990 4436
8460 1641
4116 9998
6500 2529
8545 4029
6346 5515
3618 2661
9359 2929
7134 354
1568 9403
3381 2440
...

output:

0.001961888

result:

ok found '0.00196', expected '0.00196', error '0.00000'

Test #22:

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

input:

2
0 0
1 707
2
1 0
0 706

output:

0.000001002

result:

ok found '0.00000', expected '0.00000', error '0.00000'

Test #23:

score: 0
Accepted
time: 124ms
memory: 26756kb

input:

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

output:

1.293947789

result:

ok found '1.29395', expected '1.29395', error '0.00000'

Test #24:

score: 0
Accepted
time: 51ms
memory: 15088kb

input:

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

output:

9.341945760

result:

ok found '9.34195', expected '9.34195', error '0.00000'

Test #25:

score: 0
Accepted
time: 75ms
memory: 26776kb

input:

100000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
1...

output:

0.000131372

result:

ok found '0.00013', expected '0.00013', error '0.00000'

Test #26:

score: 0
Accepted
time: 69ms
memory: 26704kb

input:

100000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
10000 10000
0 0
1...

output:

0.163473263

result:

ok found '0.16347', expected '0.16347', error '0.00000'

Test #27:

score: 0
Accepted
time: 61ms
memory: 26720kb

input:

100000
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
9992 9990
10 9
999...

output:

0.044331253

result:

ok found '0.04433', expected '0.04433', error '0.00000'