#P3327. [Scoi2013]泡泡鱼
[Scoi2013]泡泡鱼
题目描述
Fish 想在海底玩一局「泡泡鱼」。发射点为 ,区域的三道墙是 、 和 。场地里一开始有若干彩色泡泡。每个泡泡都是直径为 的圆。
相切且颜色相同的两个泡泡相邻。若两个泡泡可以沿若干个相邻泡泡连在一起,则称它们相连。
每次 Fish 从发射点向指定方向发射一个指定颜色的泡泡,角度从 轴正方向逆时针量起。泡泡沿该方向运动,到第一次与其他泡泡或任一道墙相切时停下。等它停下后,才能发射下一个。
如果新泡泡与至少两个其他泡泡相连,则包括新泡泡在内的整个同色连通块都消失。若消失的泡泡有 个,Fish 得 分。初始的连通块不会自行消失。求总得分。
输入格式
从标准输入读取。第一行两个实数 ,均精确到小数点后六位。
第二行一个整数 ,为初始泡泡数。接下来 行,第 行有两个实数 和一个整数 ,分别为泡泡圆心坐标及颜色。坐标精确到小数点后八位。
随后一行一个整数 ,为发射次数。接下来 行,每行一个实数 和一个整数 ,分别为发射角(单位为度)及颜色。角度精确到小数点后两位。
输出格式
向标准输出写入。输出一行一个整数,表示 Fish 的总得分。
样例 1
4.000000 10.000000
5
-2.00000000 9.00000000 3
1.00000000 7.26794919 10
-3.00000000 7.26794919 3
2.00000000 9.00000000 10
0.00000000 9.00000000 10
5
66.60 10
106.20 3
88.20 5
91.80 5
84.60 5
34
数据范围与约定
初始泡泡都在区域内,任意两泡泡不相交。每次发射时,发射点没有泡泡停放。
考虑浮动和浮点精度误差,若两个泡泡的圆心 、 满足
则认为它们相切。
| 数据比例 | 初始泡泡数 | 发射次数 |
|---|---|---|
| 另有 | ||
| 其余 |
所有角度满足 ;,颜色编号为 至 。