提示: 欢迎访问OurACM平台。
Problem 1887 景区摊位安排问题

Accept: 57    Submit: 133
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

一个旅游景区内有若干个摊位。景区可以看成是一个无限大的平面,然后每一个摊位(固定的)可以用一组坐标来表示。由于每一个摊位能容纳的游客数量是固定的,所以如果某一个摊位的游客满了,那么其余的游客会在附近半径为 R 的圆范围内重新寻找另一个摊位(不论人是否满) ,如果找不到,那么这些游客会很扫兴地离开;如果找到了,如果新的摊位是满的,那么继续按照上面的方法找,否则就入座。

现在已经知道景区内所有景点的坐标以及它们对应的所能容纳游客的数目。同时也知道在一段时间的人流量(既假设对于第i 个摊位,Pi 表示这段时间内走道该摊位的人数)。假设在这段时间内,游客在入座以后就不再离开。

同时,由于游客的离开会导致利润下降,于是有的店主开始考虑增加店面大小使之可以容纳更多的游客(注意,在本问题中把摊位看成一个点),然而由于不同的摊主的资金等条件不同,所以每一个摊位的座位增加量 Ai 以及 增加单位座位的花费 Ci也不同。

在一番整修之后,若人流量保持不变,那么最多有多少游客可以入座?(注意,不一定所有的摊位都会增加座位)

Input

有多组数据

数据的第一行包含一个正整数T 表示数据组数( 1 <= T <= 100) 接下来T 组数据 对于每组数据

第一行 包含 一个正整数 N 和一个实数 R 分别代表摊位个数以及题目描述中的半径R 。 (1 <= N <= 100, 0.0 <= R <= 100.0,R的小数点后至多出现3位)

接下来N 行 每行包含 2个 实数 Xi, Yi 和一个正整数Vi 分别代表第i个摊位的坐标 以及 这个摊位能容纳游客的数目 (1 <= Xi,Yi <= 100, 0 <= Vi <= 100)

数据保证不会出现坐标相同的摊位

之后接下来N 行 每行2个正整数 Ai Ci 分别表示第i个摊位的座位增加量 和增加单位座位的花费 (0 <= Ai <= 100,1 <= Ci <= 100)

接下来N行 每行只有一个整数Pi 表示这段时间内第i个摊位的人流量 (0 <= Pi <= 100)

Output

对于每组数据,首先输出”Case d: “,其中d为数据编号(从1开始).只输出两个正整数,分别表示这段时间内最多能入座的游客人数以及所以店主的花费和的最小值。

Sample Input

2 2 3.00 1 5 1 4 5 10 10 1 7 23 12 0 2 2.999 1 5 1 4 5 10 3 100 100 1 12 0

Sample Output

Case 1: 12 1 Case 2: 4 300

Hint

样例1: 方案为: 第一个摊位扩充1个位置,花费1 第二个摊位扩充0个位置,花费0 第一个摊位的12个人流量中,2人留在了第一个摊位,而余下的10名游客则到摊位2就坐 样例2: 方案为: 第一个摊位扩充3个位子,共花费 3 * 100 = 300 第二个摊位不扩充,花费0 第一个摊位的12个人流量中,4人留在了第一个摊位,而余下的游客则由于在R为半径的圆内无法找到另一个摊位而离去

Source

AekdyCoin

Submit  Back  Status  Discuss