#BZOJ3327. 泡泡鱼
-
ID: 1851
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
泡泡鱼
题目描述
Fish 是一条生活在海里的鱼，有一天他很无聊，想起了一个人类玩的游戏泡泡龙，于是他打算玩一把泡泡鱼。
Fish 并不是特别清楚泡泡龙的规则（我们也是），于是他采用自己定的近似规则。
这里我们把海底想象成一个平面区域，它的上边界离发射点距离为H，左右边界离发射点的距离均为W。起初时在这个区域的某些位置上有一些各种颜色的泡泡，且每个泡泡的直径为2（这里视泡泡为圆形）。如果两个相同颜色的泡泡相切，我们就说这两个泡泡相邻。如果两个相同颜色的泡泡相邻或者可以通过第三个相同颜色的泡泡相连，我们就说这两个泡泡相连。
为了方便描述，我们定义发射点的坐标为(0, 0)，每次Fish 会在发射点以某个给定角度发射某种颜色的泡泡。如果泡泡撞到墙壁或者其他泡泡（即在某个时间第一次与墙壁或者其他泡泡相切），这个泡泡就会停住。如果这个泡泡与超过一个泡泡相连，那么这些泡泡就会消失，而Fish 就会得到消失泡泡数量的平方的分数值。请注意，初始时如果有超过两个泡泡相连，这些泡泡并不会消失。现在已知初始泡泡的情况和每次发射泡泡的颜色和角度（相对于+x 轴逆时针方向），请你给出最终的总得分。注意，在上一次发射出去的泡泡停止之前，Fish 不能够继续发射泡泡。
输入格式
输入的第一行有两个实数W，H，表示游戏区域的边界坐标，精确到小数点后六位。
接下来一行有一个整数n，表示初始泡泡的个数。
接下来n 行，第i 行首先是两个浮点数xi 和yi，表示第i 个泡泡的圆心坐标，精确到小数点后八位，然后是一个整数ci，表示第i 个泡泡的颜色。
接下来一行有一个整数q，表示发射的泡泡的个数。
最后q 行，第i 行首先是一个浮点数ai，精确到小数点后两位，表示第i 次发射的泡泡的角度，然后是一个整数ci，表示第i 次发射的泡泡的颜色。
数据保证刚开始所有的泡泡均在区域内！
数据保证泡泡刚发射的位置永远不会停放有泡泡！
由于泡泡会在海水中浮动（以及计算机浮点的精度误差），我们认为当(xa-xb)^2 + (ya-yb)^2 <= (2 [1]* 1)^2 + 10^-6
成立时，泡泡a 和泡泡b 相切！
数据保证初始时不存在相交的泡泡
对于30% 的数据，1 <= n <= 10，1 <= q <= 10。
另有50% 的数据，1 <= n <= 1000，1 <= q <= 1000。
剩下20% 的数据，1 <= n <= 10^5，1 <= q <= 10。
对于所有的数据，有0 < a < 180，0 < W, H <= 1000，1 <= ci <= 100。
输出格式
输出只有一行，这一行只有一个整数，代表Fish 最后的总得分。
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
数据范围与约定
应上传者要求，此系列试题不公开,如有异议，本站将删除之。