#P3327. [Scoi2013]泡泡鱼

    ID: 2515 传统题 1000ms 512MiB 尝试: 64 已通过: 19 难度: 7 上传者: 标签>难度分类提高模拟与实现技巧事件驱动模拟计算几何直线与圆相交数据结构普通并查集平方距离比较懒删除均匀网格空间划分CF2300

[Scoi2013]泡泡鱼

题目描述

Fish 想在海底玩一局「泡泡鱼」。发射点为 (0,0)(0,0),区域的三道墙是 x=−Wx=-W、x=Wx=W 和 y=Hy=H。场地里一开始有若干彩色泡泡。每个泡泡都是直径为 22 的圆。

相切且颜色相同的两个泡泡相邻。若两个泡泡可以沿若干个相邻泡泡连在一起,则称它们相连。

每次 Fish 从发射点向指定方向发射一个指定颜色的泡泡,角度从 xx 轴正方向逆时针量起。泡泡沿该方向运动,到第一次与其他泡泡或任一道墙相切时停下。等它停下后,才能发射下一个。

如果新泡泡与至少两个其他泡泡相连,则包括新泡泡在内的整个同色连通块都消失。若消失的泡泡有 ss 个,Fish 得 s2s^2 分。初始的连通块不会自行消失。求总得分。

输入格式

从标准输入读取。第一行两个实数 W,HW,H,均精确到小数点后六位。

第二行一个整数 nn,为初始泡泡数。接下来 nn 行,第 ii 行有两个实数 xi,yix_i,y_i 和一个整数 cic_i,分别为泡泡圆心坐标及颜色。坐标精确到小数点后八位。

随后一行一个整数 qq,为发射次数。接下来 qq 行,每行一个实数 aa 和一个整数 cc,分别为发射角(单位为度)及颜色。角度精确到小数点后两位。

输出格式

向标准输出写入。输出一行一个整数,表示 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

数据范围与约定

初始泡泡都在区域内,任意两泡泡不相交。每次发射时,发射点没有泡泡停放。

考虑浮动和浮点精度误差,若两个泡泡的圆心 (xa,ya)(x_a,y_a)、(xb,yb)(x_b,y_b) 满足

(xa−xb)2+(ya−yb)2≤4+10−6,(x_a-x_b)^2+(y_a-y_b)^2\le4+10^{-6},

则认为它们相切。

数据比例 初始泡泡数 发射次数
30%30\% 1≤n≤101\le n\le10 1≤q≤101\le q\le10
另有 50%50\% 1≤n≤10001\le n\le1000 1≤q≤10001\le q\le1000
其余 20%20\% 1≤n≤1051\le n\le10^5 1≤q≤101\le q\le10

所有角度满足 0<a<1800<a<180;0<W,H≤10000<W,H\le1000,颜色编号为 11 至 100100。