跳到主要内容
图灵 OJTURING / ONLINE JUDGE

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

  • ID: 138
  • 传统题
  • 1000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 待分类
  • 整理状态
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

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

题目描述

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

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

  • 现在有 个玩家(包括 ZQC 自己),每个玩家有一个坐标 和活动半径 ,当前质量 。也就是每个玩家在一个圆里活动,包括边界。
    形式化地,玩家的活动范围为 。
  • 还有 个食物球,每个球有坐标 和质量 。
  • 每个玩家可以吃到自己活动范围内的食物球(不能吃其它玩家),并且可以只吃一部分,每个玩家吃每个食物球的量必须是非负整数,吃掉的部分会加在自身质量上。
    形式化地,用一个 的矩阵 来表示吃的情况,其中 表示玩家 吃食物 的量,则:
    • 有
    • ,最终的质量
    • 有
  • 由于 ZQC 非常神,她可以钦点所有玩家的行动。
    • ZQC 会将它活动范围内的所有食物球吃光。
    • 对于每个食物球,如果它在至少一个玩家的活动范围内,则它一定要被吃光。形式化地,设这个食物球编号为 ,则有

问有没有一种钦点方案使得没有其它玩家的质量比 ZQC 的更大()?


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

输入格式

第一行一个正整数 ,表示测试数据的组数。
对于每组测试数据,第一行两个正整数 。
接下来 行,每行四个整数 ,其中第一个玩家是 ZQC。
接下来 行,每行三个整数 。

输出格式

如果方案存在,输出一行 ZQC! ZQC!,否则输出一行 qaq。

样例

样例输入

2
3 2
0 0 1 10
10 0 1 10
20 0 1 10
5 0 2
15 0 4
3 2
0 0 1 10
10 0 1 10
20 0 1 10
5 0 2
15 0 5

样例输出

ZQC! ZQC!
qaq

题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 13 题。保留原作者与原赛事署名。