#P2394. 穿云箭[废题]

    ID: 1437 传统题 3000ms 256MiB 尝试: 43 已通过: 1 难度: 7 上传者: 标签>CF2200提高有限候选集缩减暴力枚举欧几里得算法二分查找高精度乘法向下取整与向上取整

穿云箭[废题]

题目描述

风行者的技能“穿云箭”可以沿一条直线穿透多个小兵。风行者现在只能射出一箭,希望获得尽可能多的金币。

平面上有 NN 个小兵。第 ii 个小兵的位置为 (Xi,Yi)(X_i,Y_i),当前生命值为 HiH_i,击杀它可以获得 GiG_i 枚金币。

风行者可以在平面上的任意位置射出一支箭,并任意选择射击方向。箭沿射击方向形成一条无限长的射线;只有位于该射线上的小兵才会中箭。小兵按照箭前进方向上的位置顺序依次中箭。

  • 第一个中箭的小兵受到 BB 点伤害。

  • 对于第 kk 个中箭的小兵(k≥1k\ge 1),它受到的伤害为

    Dk=B(1−P100)k−1.D_k=B\left(1-\frac{P}{100}\right)^{k-1}.

    即每穿过一个小兵,后续伤害都变为前一次的 (100−P)%(100-P)\%。

  • 无论此前的小兵是否被击杀,只要中箭,就会使后续伤害衰减一次。

  • 若某小兵中箭后剩余生命值 Hi−Dk≤0H_i-D_k\le 0,则认为它被击杀,可以获得 GiG_i 枚金币。金币只计算一次。

保证任意两个小兵的位置不同。 因此,同一射线上各小兵的中箭顺序确定。允许生命值、金币数或初始伤害为 00;当小兵生命值为 00 时,只要中箭,仍按上述条件判定为被击杀。

求风行者只射出一箭最多可以获得多少枚金币。允许选择不命中任何小兵,此时获得 00 枚金币。

输入格式

第一行包含三个整数 N,B,PN,B,P。

接下来 NN 行,每行包含四个整数 Xi,Yi,Hi,GiX_i,Y_i,H_i,G_i,分别表示第 ii 个小兵的坐标、生命值以及击杀获得的金币。

输出格式

输出一个整数,表示一箭能够获得的最多金币数。

样例 1

输入

1 1 1
1 1 1 1

输出

1

样例 2

输入

6 2 1
2 2 1 1
1 1 1 1
3 3 1 1
1 3 1 1
1 2 1 1
3 1 1 1

输出

3

说明

从 (1,1)(1,1) 之前向 (3,3)(3,3) 的方向射击,可以依次命中 (1,1)(1,1)、(2,2)(2,2)、(3,3)(3,3) 三个小兵。它们依次受到 22、1.981.98 和 1.96021.9602 点伤害,均能够被击杀,共获得 33 枚金币。

数据范围与约定

  • 1≤N≤10001\le N\le 1000;
  • 0≤B≤1040\le B\le 10^4;
  • 0≤P≤990\le P\le 99;
  • 0≤Xi,Yi,Hi,Gi≤1040\le X_i,Y_i,H_i,G_i\le 10^4;
  • 任意两个小兵的坐标互不相同。

数据分布参考原题:约 20%20\% 的测试数据满足 N≤20N\le20;约 50%50\% 的测试数据满足 N≤100,B≤100,P≤50N\le100, B\le100, P\le50。本修订版测试数据主要按边界与算法正确性设计,并不以这些比例构造评分子任务。