QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#801364 | #4769. Keeping the Dogs Apart | LeGusto | AC ✓ | 144ms | 26820kb | C++14 | 5.1kb | 2024-12-06 21:50:30 | 2024-12-06 21:50:31 |
Judging History
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'