Skip to content

enchained/hh_min_distance

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

8 Commits
 
 
 
 
 
 
 
 

Repository files navigation

1. Минимальное расстояние

Дан набор из N точек на плоскости (для простоты можно считать, что у всех точек целочисленные координаты). Найдите минимальное расстояние между двумя точками из этого набора.

Пример входных данных:
10 10
20 10
20 15

Пример выходных данных:
5

Запуск программы:

python min_distance.py points.txt

Формат файла points.txt:

10 10  
20 10  
20 15  

Пример результата:

>>>
(10, 10)
(20, 10)
(20, 15)
Minimum distance between points is 5

Запуск тестов:

python min_distance_test.py -v

Тесты проводятся на примере из задания, также сравниваются результаты брутфорс- и divide-and-conqer-решения для наборов случайных точек.

Пример вывода:

>>>
test_div_n_conq (__main__.FindMinDistTests) ... ok
test_from_example (__main__.FindMinDistTests) ... ok

----------------------------------------------------------------------
Ran 2 tests in 1.608s

OK

Ранняя брутфорс-версия решения являлась крайне неэффективной для больших наборов точек - ее сложность составляла O(n^2). Для оптимизации было принято решение использовать рекурсивный divide and conquer алгоритм со сложностью O(n log n), основаясь на данной статье: Closest pair of points problem.

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages