На плоскости отмечены несколько красных, синих и черных точек. Требуется покрасить каждую черную точку в красный или синий цвет так, чтобы сумма расстояний между всеми парами красных точек и расстояний между всем парами синих точек было минимальным. На вход подается csv-файл, в первой строке которого записаны заголовки столбцов: id,x,y,color
Входные данные
В каждой из остальных строк записана информация об одной из точек: id, x и y — целые числа, color — 0 для черных точек, 1 для красных точек и 2 для синих.
Общее количество точек не превосходит 15.
Выходные данные
Выведите одно число — минимальную сумму расстояний между всеми парами красных точек и расстояний между всем парами синих точек с точностью не менее пяти знаков после запятой.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
id,x,y,color
1,1,0,1
2,2,0,2
3,3,0,0
4,4,0,0 |
4.0 |