1247: #505. 「LibreOJ β Round」ZQC 的游戏

Agar.io 是一款流行的游戏，每个玩家在二维平面上控制一个球。

我们对游戏进行下列简化：

• 现在有 $n(1\le n\le 100)$ 个玩家（包括 ZQC 自己），每个玩家有一个坐标 $(x,y)$ 和活动半径 $r(0\le x,y,r\le 10000)$，当前质量 $w(1\le w\le 10000)$。也就是每个玩家在一个圆里活动，包括边界。
  形式化地，玩家的活动范围为 S={(a,b)∣(a−x)2+(b−y)2≤r2,a∈R,b∈R}S=\{(a,b)|(a-x)^2+(b-y)^2\leq r^2,a\in \mathbb{R},b\in \mathbb{R}\}S={(a,b)∣(a−x)​2​​+(b−y)​2​​≤r​2​​,a∈R,b∈R}。
• 还有 $m(1\le m\le 400)$ 个食物球，每个球有坐标 (xf,yf)(0≤xf,yf≤10000) (x_f, y_f)(0 \leq x_f, y_f \leq 10000) (x​f​​,y​f​​)(0≤x​f​​,y​f​​≤10000) 和质量 wf(1≤wf≤10000) w_f(1 \leq w_f \leq 10000) w​f​​(1≤w​f​​≤10000)。
• 每个玩家可以吃到自己活动范围内的食物球（不能吃其它玩家），并且可以只吃一部分，每个玩家吃每个食物球的量必须是非负整数，吃掉的部分会加在自身质量上。
  形式化地，用一个 $n\times m$ 的矩阵 $A$ 来表示吃的情况，其中 AijA_{ij}A​ij​​ 表示玩家 $i$ 吃食物 $j$ 的量，则：
  • $\forall i,j$ 有 Aij∈NA_{ij}\in \mathbb{N}A​ij​​∈N
  • $\forall i$，最终的质量 wni=wi+∑j=1mAijw_{\text{n}i}=w_i+\sum_{j=1}^m A_{ij}w​ni​​=w​i​​+∑​j=1​m​​A​ij​​
  • $\forall j$ 有 ∑i=1nAij≤wfj\sum_{i=1}^n A_{ij}\leq {w_f}_j∑​i=1​n​​A​ij​​≤w​f​​​j​​
• 由于 ZQC 非常神，她可以钦点所有玩家的行动。
  • ZQC 会将它活动范围内的所有食物球吃光。
  • 对于每个食物球，如果它在至少一个玩家的活动范围内，则它一定要被吃光。形式化地，设这个食物球编号为 $j$，则有 ∑i=1nAij=wfj\sum_{i=1}^n A_{ij}= {w_f}_j∑​i=1​n​​A​ij​​=w​f​​​j​​

问有没有一种钦点方案使得没有其它玩家的质量比 ZQC 的更大（∀i,wni≤wn1\forall i,w_{\text{n}i}\leq w_{\text{n}1}∀i,w​ni​​≤w​n1​​）？

一句话题意：问是否存在一种分配方案使得所有能被吃到的食物球都被吃光，并且满足 ZQC 是最♂大的玩家（之一）。