编程介的小学生 2019-08-15 21:47 采纳率: 20.5%
浏览 97

Settling Salesman Problem是怎么解答的

Problem Description
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 - xi| + |y - yi|, where (x, y) and (xi, yi) 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 xi and yi (-1 000 000 000 <= xi, yi <= 1 000 000 000): 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

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题