НачалоПодразделы
Другие разделы
| 790. Word Ladder |
| 791. Bonus Word |
| 792. Contest |
| 793. Cycling |
| 794. Escape |
| 796. Space |
| 797. Herbert |
Дата и время
17/11/2024 03:23:36
795. Settling Salesman Problem
Задача
Жадные алгоритмыПоиск в ширину (BFS)
Олимпиадные задачи на английском языке
| 08/02/2008 | Тренировка (задачи Benelux APC preliminary 2007) (F) |
| 11/07/2013 | Лето 2013-8 (F) |
Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
After travelling around for years, Salesman John has decided to settle. He wants to build
a new house close to his customers, so he doesn’t have to travel as much any more. Luckily
John knows the location of all of his customers.
All of the customers’ locations are at (distinct) integer coordinates. John’s new house
should also be built on integer coordinates, which cannot be the same as any of the customers’ locations. Since John lives in a large and crowded city, the travelling distance to
any customer is the Manhattan distance: `|x\ -\ x_i|\ +\ |y\ -\ y_i|`, where `(x,\ y)` and `(x_i,\ y_i)` are
the coordinates of the new house and a customer respectively.
What is the number of locations where John could settle, so the sum of the distance to all
of his customers is as low as posible?
Input
On the first line an integer `t` (`1\ ≤\ t\ ≤\ 100`): the number of test cases. Then for each test
case:
- One line with an integer `n` (`1\ ≤\ n\ ≤\ 2\ 000`): the number of customers John has.
- `n` lines with two integers `x_i` and `y_i` (`-10^9\ ≤\ x_i,\ y_i\ ≤\ 10^9`): the coordinates of the `i`-th customer.
Output
For each test case:
- Two space-separated integers: the minimum summed distance to all customers, and the number of spots on which John can build his new house to achieve this minimum.
Sample input
2 4 1 -3 0 1 -2 1 1 -1 2 -999888777 1000000000 1000000000 -987654321
Sample output
10 4 3987543098 3975087573110998514
