2 shunfurh shunfurh 于 2017.09.17 00:37 提问

Phone Home

When relay towers for mobile telephones communicate with the mobile phones in their area, there is always the possibility of interference. So, when assigning the transmission frequency, the FCC makes sure that nearby towers have frequencies that aren't too close. On the other hand, the FCC does not want to assign too many different frequencies; they want to save as many as possible for other uses. Your job is to find an optimal assignment of frequencies.
In this problem, the frequencies will be integers. Nearby towers must be assigned frequencies that differ by at least 2. You'll find an assignment using as few frequencies as possible. For example, consider the following two arrangements of towers. Two towers near each other are indicated by the connecting line.

Note that the following are legal frequency assignments to these two tower configurations. However, the second arrangement does not use the fewest number of frequencies possible, since the tower with frequency 5 could have frequency 1.

Input

There will be multiple test cases. Input for each test case will consist of two lines: the first line will contain the integer n, indicating the number of towers. The next line will be of the form x1 y1 x2 y2 ... xn yn where xi yi are the coordinates of tower i. A pair of towers are considered "near" each other if the distance between them is no more than 20. There will be no more than 12 towers and no tower will have more than 4 towers near it. A value of n = 0 indicates end of input.

Output

For each test case, you should print one line in the format:

The towers in case n can be covered in f frequencies.

where you determine the value for f. The case numbers, n, will start at 1.

Sample Input

5
0 0 5 7.5 1 -3 10.75 -20.1 12.01 -22
6
0 1 19 0 38 1 38 21 19 22 0 21
0

Sample Output

The towers in case 1 can be covered in 3 frequencies.
The towers in case 2 can be covered in 2 frequencies.

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.30 21:39
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Sicily.1039 Phone Home
•  深度搜索。 •  思路很明确:通过给出的数据构建出如题所示的图,然后以一个结点为种子进行深搜。 •  我使用一个二维数组(mark)来表示这个图,使用一个一维数组(num)来记录每个结点对应的值;以点对的形式输入,在这里我构建了一个类Pair,当然也可以尝试使用map; DFS的过程:先初始化第0个结点(第一组输入的数据就是第0个结点),num[0] = 1,cnt = 1(编号数);
Sicily 1039. Phone Home
<br />其实这道题难度不大的,只不过图论的染色问题好久没写过了(记得上次写估计还是高一吧...),所以写的时候又查了些时间,现在写完了,就干脆记到这吧~<br /> <br />这道题要求相邻(距离不大于20)的两个塔之间的频段不相同,即可以与着色问题相联系,即相邻两个点的颜色不同,这样这道题就成了典型的着色问题。<br /> <br />直接看代码注释解释更方便:<br />#include <iostream> #include <cstring> using namespace std; i
1039. Phone Home
Constraints Time Limit: 1 secs, Memory Limit: 32 MB Description When relay towers for mobile telephones communicate with the mobile phones in their area, there is always the possibility of interfe
[RK3288][Android6.0] 调试笔记 --- 屏蔽Home/Back Key
Platform: Rockchip OS: Android 6.0 Kernel: 3.10.92有些特殊场景需求需要屏蔽系统key, 比如home/back key,可以直接从input framework下手,改动如下:kris@:~/rk3288/frameworks/native$ g df 07a894bb62e767f3409cf1434d69af69fc253485 b26fc0
搜索 HOJ 1266 Phone Home
Phone HomeMy Tags  (Edit)Source : ACM ICPC East Central North America 2003Time limit : 1 secMemory limit : 32 MSubmitted : 49, Accepted : 36When relay towers for mobile telephones communicate with the
[SOJ1039]Phone Home(深搜,染色问题)
题目如下: (如果能看懂,就看;看不懂的话,再努力把看懂,意思就是标题,染色问题) 染色问题就是说,离散的点之间,如果有关联的点,这个两个点就不能是同样的颜色 然后回答最少用多少种颜色。 InputThere will be multiple test cases. Input for each test case will consist of two lines: the first l
POJ 1620 Phone Home 笔记
如图,顶点表示通信塔,边表示两个塔相邻,顶点上的数字表示频率。给出n个塔架的坐标,塔架相距20以内表示相邻。求最少用多少个频率。
Android Phone进程启动过程详解
之前解决开机搜网慢的问题时,由于Phone进程起来以后,才会主动连接RILD,因而在一定程度上Phone进程启动的时间会影响网络状态注册的快慢,适当的将Phone进程提前,可以将网络注册时间提前一点,让状态栏中信号显示的时间提前。那么,Android中作为系统的核心进程之一,Phone进程是如何启动的了?zui RIL运行机制请参考: http://blog.csdn.net/jason_wzn
Android Phone系统架构1
在android系统中rild运行在AP上,AP上的应用通过rild发送AT指令给BP,BP接收到信息后又通过rild传送给AP。AP与BP之间有两种通信方式: 1.Solicited Response:Ap向Bp发送请求,Bp给Ap发送回复,该类型的AT指令及其回调函数以数组的形式存放在Ril_commands.h文件中:     {数组中的索引号,请求回调函数,响应回调函数
what is RCS/RCS-e
IMS/SIP - RCS/RCS-e                                   Home : www.sharetechnote.com     RCS/RCS-e   As more and more people gets interested in IMS more than the simple SMS, I am hear