Python-сообщество

Есть анимация движения роя из N коптеров, для каждого из которых в любой момент времени известны координаты x, y, z. Нумерация кадров начинается с 0, количество кадров анимации равно M. Необходимо определить не сближаются ли какие-либо 2 дрона более, чем на 2 метра, и, если сближаются, то определить расстояние максимального сближения и кадр, на котором это сближение произошло. Если критического сближения не произошло, вернуть значение ‘-1’. Перемещения дронов между точками анимации считать мгновенным (без учета траектории полета между точками; считать, что коптеры мгновенно оказываются в конечных точках).

Формат входных данных

Во входных данных указаны значения N и M, два перевода строки, затем списки позиций дронов для каждого кадра анимации. Списки для каждого из дронов разделены двумя переводами строки.

Формат выходных данных

Необходимо вывести минимальное значение расстояния и соответствующий кадр анимации, либо значение -1.

Погрешности, которые могут возникнуть в числах с плавающей точкой, учитываются в проверке (предусмотрен допуск).

Sample Input:
23 16

-0.645 1.541 1.762
-2.018 2.315 2.882
-2.493 1.866 3.234
-3.666 3.807 3.96
-4.033 4.497 6.185
-3.738 5.952 7.134
-4.064 7.42 8.706
-4.729 9.504 8.965
-4.411 11.443 10.815
-4.966 11.229 11.399
-6.329 13.06 12.366
-7.483 13.291 12.799
-7.556 12.112 13.732
-8.071 12.127 14.809
-7.413 13.4 17.342
-7.947 13.372 17.998

14.053 1.623 5.978
14.769 1.976 6.353
14.358 3.299 7.747
13.776 2.78 9.936
14.192 4.441 12.388
13.548 3.962 14.116
13.609 2.764 15.248
14.249 1.926 16.487
12.858 3.215 18.288
12.958 3.642 19.278
12.757 2.111 20.973
13.388 1.146 20.992
12.162 0.545 21.749
10.747 0.735 24.044
10.221 2.987 24.389
10.88 4.071 26.531

15.369 14.821 12.829
15.927 13.198 13.769
14.999 12.19 14.811
14.153 14.03 16.68
13.414 12.85 18.464
12.667 14.677 20.404
11.457 16.626 20.643
10.328 17.098 22.952
9.202 17.496 24.872
8.761 17.675 25.588
8.275 17.736 28.033
8.36 15.787 30.257
7.72 14.328 30.925
7.301 13.969 32.797
7.366 12.928 34.135
6.549 11.875 36.414

2.206 14.007 15.605
2.899 16.195 15.743
2.591 16.624 17.048
1.957 17.367 17.347
2.247 19.119 18.502
2.763 21.025 20.723
1.46 20.186 21.238
-0.03 21.044 23.546
-1.304 23.534 24.849
-1.365 24.079 27.391
-1.297 24.269 28.998
-1.971 23.141 30.757
-3.072 21.539 33.135
-2.602 22.569 33.596
-2.629 23.879 34.578
-3.631 22.653 35.132

6.871 18.125 10.173
5.811 16.17 10.585
4.714 15.332 12.024
3.994 14.568 13.537
4.72 16.438 14.531
3.564 14.964 15.562
2.488 17.217 16.799
1.208 15.354 17.95
1.482 16.058 20.226
0.221 15.624 20.663
0.495 14.615 23.017
1.279 14.276 24.969
1.683 16.872 26.481
2.411 15.932 28.082
2.399 14.536 29.176
2.689 12.582 30.798

2.454 3.654 11.803
1.352 5.614 12.077
0.102 7.353 13.686
0.119 9.348 14.717
-0.062 9.334 16.951
-0.213 8.952 19.299
-1.338 9.674 21.319
-0.698 10.297 22.619
-1.597 11.41 24.333
-1.131 12.8 26.599
-0.892 14.646 27.791
-1.16 15.605 28.947
-0.681 17.098 30.421
-1.762 15.698 32.181
-1.243 15.936 34.269
-1.044 14.078 35.811

17.138 6.097 11.574
16.421 8.375 12.59
17.192 10.197 14.458
16.692 8.485 15.285
16.155 7.214 16.899
14.926 6.429 19.471
15.26 5.137 21.908
13.846 6.722 23.995
12.907 6.344 25.61
13.392 5.538 26.333
13.179 8.084 26.795
13.142 6.969 28.849
13.701 8.02 29.991
14.339 9.912 30.329
14.808 10.812 31.332
14.778 9.76 32.227

12.269 7.347 17.381
11.905 7.336 19.629
11.458 5.453 20.156
10.286 3.654 20.243
11.047 4.875 21.345
10.204 3.6 22.637
9.962 2.728 24.459
10.558 3.395 25.247
11.13 4.599 26.59
10.173 4.48 26.659
9.06 5.411 28.169
8.055 3.615 30.411
7.675 3.409 31.262
7.859 4.099 33.238
7.852 5.632 34.971
8.046 3.852 35.426

17.341 15.51 6.79
16.226 16.44 8.14
16.485 16.682 9.064
17.156 16.942 9.582
15.992 16.048 10.043
14.919 15.488 12.077
13.852 14.815 13.715
14.168 14.18 14.189
12.791 13.951 14.656
12.825 12.887 16.04
11.872 14.353 18.238
10.68 15.593 18.853
10.769 16.825 20.286
9.385 17.957 22.192
8.484 19.155 23.876
8.517 21.617 24.166

0.027 9.662 4.123
-0.831 11.368 5.701
-2.329 10.772 6.295
-3.484 11.438 6.532
-3.761 13.996 8.83
-5.213 16.413 10.419
-6.232 18.569 12.844
-7.122 16.614 14.072
-6.563 14.795 15.836
-6.113 13.731 17.863
-5.427 15.667 19.249
-4.719 13.701 19.517
-5.346 12.064 22.059
-5.05 12.114 24.031
-5.429 10.536 24.471
-6.463 8.651 24.975

10.21 4.081 19.744
10.111 2.873 22.131
9.241 1.214 22.833
9.627 3.748 23.285
9.982 2.854 24.83
8.588 3.543 26.315
8.008 4.956 27.493
6.708 5.072 30.072
6.914 5.2 32.301
7.318 6.561 34.328
6.614 4.685 36.611
7.238 4.606 39.129
7.793 6.275 40.339
6.716 7.844 42.342
5.664 10.175 44.907
4.772 8.895 46.63

2.537 15.789 4.899
2.885 14.565 6.385
2.645 16.489 6.479
1.487 16.88 7.053
2.052 15.52 9.355
1.64 14.916 11.624
0.874 13.032 11.868
-0.322 11.328 12.337
-1.739 13.753 14.291
-1.524 16.155 15.881
-1.835 17.611 17.267
-3.11 16.156 19.639
-2.349 18.007 20.981
-2.757 19.827 21.857
-2.361 20.396 22.875
-3.14 18.865 24.63

18.311 2.834 6.297
18.706 0.936 7.422
18.961 1.872 8.174
17.638 1.886 8.97
16.714 -0.057 11.401
16.915 -0.845 13.445
15.729 -2.325 14.721
15.138 -4.271 17.169
14.335 -4.231 18.547
14.64 -2.792 18.573
14.788 -2.986 19.412
14.003 -4.405 21.2
14.776 -3.509 21.247
13.744 -3.19 23.265
13.185 -4.325 23.303
13.243 -2.23 24.273

11.347 21.434 6.638
11.432 21.85 8.371
11.177 23.189 10.009
10.791 24.702 10.661
11.157 27.114 10.707
10.695 28.674 11.777
10.386 31.111 14.135
11.106 31.935 16.483
10.685 30.885 19.043
10.174 32.911 19.227
9.653 34.325 20.741
8.876 35.914 23.279
8.741 37.321 24.123
9.467 38.867 24.37
8.845 40.312 25.088
8.034 41.121 27.084

6.479 18.643 10.503
6.837 17.612 10.74
5.848 17.968 10.864
4.952 16.233 13.071
3.471 16.598 14.015
2.973 17.243 14.177
1.742 18.483 14.783
1.994 17.182 16.71
2.152 18.036 16.798
2.435 18.687 17.671
1.425 19.281 20.108
0.529 17.683 22.368
1.194 19.573 23.011
0.583 19.253 23.076
0.297 19.47 24.253
-0.409 19.526 25.85

2.687 2.114 15.262
1.428 0.868 17.486
1.168 1.423 18.935
0.888 1.316 19.531
0.981 2.03 21.918
1.102 0.736 23.175
1.26 -1.106 24.227
0.878 -0.475 26.599
0.997 -1.898 28.151
0.72 -2.481 28.823
0.489 -1.812 29.621
-0.083 -3.241 30.468
-1.339 -1.827 31.633
-1.424 -2.659 32.567
-2.735 -1.984 33.886
-2.084 -3.56 35.637

5.883 15.566 10.99
5.134 16.609 11.784
5.887 17.853 12.289
4.893 19.193 14.537
4.342 18.37 15.164
3.079 19.066 15.253
2.389 20.75 16.856
2.642 22.694 19.101
2.784 23.925 19.676
2.141 24.106 21.566
1.341 25.994 23.101
1.873 25.967 23.492
0.432 26.278 23.498
0.432 27.112 25.006
-0.414 27.045 25.947
-1.873 25.98 27.625

0.184 17.769 2.502
-0.33 19.914 5.076
-1.581 18.883 5.657
-2.333 18.319 6.146
-3.597 18.335 6.607
-3.438 18.135 8.78
-4.749 20.495 11.371
-4.934 22.398 13.082
-4.788 21.402 13.412
-4.543 21.263 13.573
-4.883 21.269 13.944
-4.462 20.584 14.409
-5.608 19.844 15.822
-5.523 18.634 16.165
-5.179 19.61 17.077
-6.15 18.354 19.269

16.511 11.034 18.4
17.094 11.854 20.42
16.872 11.13 20.593
15.703 10.737 22.349
14.419 12.237 24.599
14.9 12.382 27.198
15.072 13.142 29.776
14.616 11.755 30.84
13.693 10.502 31.996
13.87 9.367 33.22
12.699 8.207 34.22
13.139 9.849 35.997
12.521 10.092 37.201
13.098 8.338 39.329
11.669 6.659 41.072
12.026 5.148 41.303

15.781 5.575 20.003
15.493 7.345 20.005
16.26 9.791 20.638
15.495 9.011 20.698
15.513 9.34 23.191
15.446 11.552 23.233
15.499 10.522 23.591
15.557 12.796 25.238
14.851 13.067 25.966
15.198 13.994 26.699
14.252 16.24 28.428
14.511 18.137 30.222
14.937 18.821 31.98
13.534 20.629 34.405
14.167 20.804 35.16
13.114 23.013 37.643

11.363 2.759 19.285
11.823 1.067 21.24
10.44 -0.85 21.764
10.213 -0.329 23.019
9.952 -0.559 24.294
10.119 1.584 24.66
9.675 0.885 25.509
9.989 2.33 27.07
9.005 3.904 28.445
9.353 5.363 29.376
9.526 5.698 29.732
8.559 7.691 31.271
9.338 7.238 33.081
8.346 5.869 35.042
7.939 4.252 36.559
8.077 2.651 37.078

7.404 1.263 21.591
8.05 0.319 21.641
6.553 -0.29 21.814
6.749 -1.542 23.457
7.538 -3.346 24.94
8.222 -1.515 25.966
6.865 -2.303 27.036
5.532 -1.615 29.396
4.603 0.05 31.672
5.348 0.338 32.116
5.163 2.824 33.165
5.922 3.584 34.644
5.396 1.61 36.072
4.368 3.793 36.766
2.976 4.199 36.893
3.681 3.54 38.957

11.265 12.628 13.633
10.422 13.226 15.231
10.38 13.06 15.83
10.853 11.287 16.924
11.497 11.402 18.315
11.097 11.579 19.696
11.214 14.016 22.204
10.184 14.162 23.069
9.301 15.778 25.002
9.489 14.293 26.877
9.056 16.394 27.615
8.21 14.901 28.635
7.079 15.104 31.224
6.786 16.979 32.157
7.465 18.403 33.622
7.406 19.416 35.246

Sample Output:
0.7286206145862202 0

Отредактировано BiboEsh (Дек. 26, 2018 04:07:03)

Расстояние между двумя точками в пространстве

  
>>> def distance(x1, y1, z1, x2, y2, z2):
...     return ((x2 - x1) ** 2 + (y2 - y1) ** 2 + (z2 - z1) ** 2) ** 0.5
... 
>>> distance(0.0, 0.0, 0.0, 1.0, 1.0, 1.0)
1.7320508075688772
>>>