Wireless Communication Base Stations
Time limit2sMemory limit128 MB
Assign positive integer frequencies to at most 12 base stations so adjacent stations (within distance 20) differ by at least 2, minimizing the count of distinct frequencies used.
- Level
Medium6 of 10
- Topics
- Backtracking, Graph, Brute force
- Solved
- No attempts yet
Problem
A city has N wireless communication base stations. Each base station has a distinct position represented by its x and y coordinates.
Base stations communicate using radio waves at selected frequencies. If the distance between two base stations is at most 20, the two stations are considered adjacent. Adjacent stations must use different frequencies to avoid interference. Moreover, because similar frequencies can also cause communication problems, the two frequencies must differ by at least 2. For this problem, only positive integer frequencies are considered.
When building wireless communication devices, it is better to support fewer kinds of frequencies, because every frequency that may be used must be handled.
Given the positions of the base stations, determine the minimum number of different frequency types that must be used.
Input
The first line contains N (1 <= N <= 12). Each of the next N lines contains the coordinates of one base station as real numbers.
The stations are spread out enough that each station is adjacent to at most 4 other stations. Each coordinate has absolute value at most 200 and is given with at most two digits after the decimal point.
Output
Print the minimum number of different frequency types on the first line.