首页 > ACM题库 > HDU-杭电 > hdu 3703 Disconnect待解决[解题报告]C++
2015
02-21

hdu 3703 Disconnect待解决[解题报告]C++

Disconnect

问题描述 :

An enemy state of our country is occupying an island of ours. They take lots of warships around the island. Communications among the warships are transited by wireless signal, but we have to separate the warships so that at least ONE pair of warships cannot communicate with each other.
For that purpose, we create a kind of Wireless Signal Shielding Device (WSSD) that WSSD can shield the wireless signal in its shielding circle with radius R.
The factories could produce enough WSSDs and our patrol team discovered a lot of places that could be installed with WSSDs. In order to separate the warships, we need to know the minimum value of radius R, smaller R is better because of the cost of manufacture.
Please notice that because of the inflection of wireless signal, two warships can communicate with each other even there is no sight view between them.

输入:

The input contains multiply test cases.
The first line of each test case consists of two integers, n, m (0 < n, m <= 10000), which are the number of places where we can install WSSDs and the number of warships. Each of the next n lines contains two integers, indicating the coordinate of the place where we can install WSSDs. The next m lines indicate the coordinates of warships.
The last test case is followed by a single line with two zeros which should not be processed.
Please notice that all the values of coordinates are between -10000 to 10000, and no two coordinates have the same value.

输出:

The input contains multiply test cases.
The first line of each test case consists of two integers, n, m (0 < n, m <= 10000), which are the number of places where we can install WSSDs and the number of warships. Each of the next n lines contains two integers, indicating the coordinate of the place where we can install WSSDs. The next m lines indicate the coordinates of warships.
The last test case is followed by a single line with two zeros which should not be processed.
Please notice that all the values of coordinates are between -10000 to 10000, and no two coordinates have the same value.

样例输入:

4 3
-1 0
1 0
0 1
0 -1
10 0
9 0
0 0
4 3
-1 0
1 0
0 1
0 -1
10 0
9 0
-9 0
0 0

样例输出:

0.71
8.00


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法