Back to Category
d188: [11.09] E - Minimum Disc Cover Set
Keyword:

Difficulity: N/A | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 3 Times | Submit :6 Times | Clicks : 845
Accepted : 1 Users | Submit : 1 Users | Accepted rate : 100%
Time Limit :5000 ms | Memory Limit : 64000 KBytes
Update : 2012-04-09 13:14

Content: English | Chinese(TW)

A set of discs with the same radius are placed randomly such that their centers are all located inside the first disc. Compute the minimum subset of these discs such that the union of the discs in the subset will cover all of the discs.

For instance, there are 7 discs in Figure . All of their centers are located inside disc 0. We can see clearly that the union of disc 1, 2, 4, 5, and 6 (marked by red circles) covers all of the discs. Additionally, none of disc 1, 2, 4, 5, and 6 can be completely covered by other discs. Therefore, the minimum disc cover set for these 7 discs is {1, 2, 4, 5, 6}.

Technical Specification

The following assumptions are provided for simplicity.

  1. The radius of discs is assumed to be 10.
  2. The x and y coordinates of the center of each disc are assumed to be integers.
  3. No two discs are exactly co-located.
  4. The maximum number of discs is 20. 

Input:

There will be multiple test cases, each on its own line. For each case instance, the first integer represents the total number of discs for this case, which is then followed by the x and y coordinates of the center of each disc. All these numbers are separated by a blank. A change-of-line indicates the end of a test case. Notice that the index of discs starts from 0 and all of the centers are located inside disc 0.

Output:

For each test case, print the result in a single line to the standard output (i.e., screen). The output should contain the indexes of the discs in the minimum disc cover set, separated by a blank. Note that the disc 0 (where the centers of all other discs are located) should not be included in the output regardless whether it is in the minimum disc cover set or not.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
7 0 0 -10 0 0 10 5 0 0 -10 8 5 8 0

Sample Output :

1 2 4 5 6

Hint :

Author :


  Solve it!   Status Forum

C
C++
JAVA
PASCAL
45511. rabbit125
(2ms, 780KB, 1659B)

Program running time may be affected by various factors. Check server system environment information here