编程介的小学生 2020-01-07 00:55 采纳率: 20.5%
浏览 60

Guard 的设计的问题

Problem Description

The Bluewater Security Company provides guards for clients with valuable possessions. Bluewater has found that clients are interested in having guards posted where they can see everything that is valuable merely by turning their heads, and also like guards to be posted particularly close to particularly valuable items. A sample site layout is shown above. Ignore the three black dots for now. Various locations are labeled and assigned values. For instance location A at coordinates (0,8) is the position of an item with value 4. Locations showing a value 0, like G, do not have a valuable item. The straight lines indicate corridors. For simplicity, corridors are modeled as line segments with 0 width. A guard at an intersection point of several corridors can see and therefore guard the items on each of the corridors. If Bluewater were contracted to supply 3 guards, they might choose to post them at the positions indicated with the small black dots. The guard not at an already labeled position is at (15.5, 6). To model the desire for guards to be closer to items of higher value, Bluewater calculates the risk to a valuable item to be the value of the item times the minimum distance to a guard that can see the item. Even if a guard is close to an item that is around a corner, that guard does not affect the risk to the item, since the guard cannot see around a corner. In the diagram shown, the risks to the items are A: 4x5=20, C: 4x2.5=10, D: 2x0=0, .... The largest risks are for H: 50x7.5=375 and I: 50x7.5=375, so the maximum risk to any one item is 375. With this site layout, no arrangement of 3 guards would provide a lower maximum risk, so this arrangement of 3 guards minimizes the maximum risk. Bluewater would like to be able to tell any client who requests a particular number of guards for a particular site layout, what the minimized maximum risk will be.

Input
The input will consist of one to sixteen data sets, followed by a line containing only 0. On each line the data will consist of blank separated tokens.

The first line of a dataset contains integers p c g, where p is the number of points specified, c is the number of corridors, and g is the number of guards to be placed. Constraints are 1< p < 12; 0 < c < 12; 0 < g < 5.

Next in the dataset are a total of p groups of four tokens, each consisting of a capital letter and three nonnegative integers L x y v indicating the point (x, y) with label L contains an item with value v. If p is no greater than 6, these groups will all be on one line. If p is greater than 6, then the seventh and further groups will be on the next line. Labels will be consecutive letters starting from A. All the numbers are less than 1000. Each of the points is unique. A value of 0 for v means there is no item of value there. The number of locations with items of value will be at least as large as the number of guards.

The last line of a dataset contains c strings of letters, one for each corridor. For each corridor the letters are labels for points along the corridor, in order along the line segment from one end to the other, including both endpoints, all intersection points with other corridors, and all locations on the corridor with a valuable item. Each of the points given in the dataset will lie on at least one of the corridors.

Output
There is one line of output for each data set. If there are not enough guards supplied to be able to see all the valuables, the line is "too few guards". Otherwise the line is an unsigned number r rounded to two places beyond the decimal point, where r is the minimum value over all placements of g guards of the maximum "risk" to the valuables.

Sample Input
11 5 3
A 0 8 4 B 5 8 0 C 14 8 4 D 21 8 2 E 25 8 1 F 5 22 1
G 5 20 0 H 11 12 50 I 20 0 50 J 19 10 5 K 25 4 5
ABCDE AG FGB GHCI JDK
11 5 2
A 0 8 4 B 5 8 0 C 14 8 4 D 21 8 2 E 25 8 1 F 5 22 1
G 5 20 0 H 11 12 50 I 20 0 50 J 19 10 5 K 25 4 5
ABCDE AG FGB GHCI JDK
11 5 1
A 0 8 4 B 5 8 0 C 14 8 4 D 21 8 2 E 25 8 1 F 5 22 1
G 5 20 0 H 11 12 50 I 20 0 50 J 19 10 5 K 25 4 5
ABCDE AG FGB GHCI JDK
11 5 4
A 0 8 4 B 5 8 0 C 14 8 4 D 21 8 2 E 25 8 1 F 5 22 1
G 5 20 0 H 11 12 50 I 20 0 50 J 19 10 5 K 25 4 5
ABCDE AG FGB GHCI JDK
3 3 1
A 0 0 50 B 0 3 60 C 4 0 20
AB CB CA
0

Sample Output
375.00
1250.00
too few guards
21.21
150.00

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

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