OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SCOI2013】泡泡鱼

【题目描述】

Fish是一条生活在海里的鱼,有一天他很无聊,想起了一个人类玩的游戏泡泡龙,于是他打算玩一把泡泡鱼。

Fish并不是特别清楚泡泡龙的规则(我们也是),于是他采用自己定的近似规则。

这里我们把海底想象成一个平面区域,它的上边界离发射点距离为H,左右边界离发射点的距离均为W。起初时在这个区域的某些位置上有一些各种颜色的泡泡, 且每个泡泡的直径为2(这里视泡泡为圆形)。如果两个相同颜色的泡泡相切,我们就说这两个泡泡相邻。 如果两个相同颜色的泡泡相邻或者可以通过第三个相同颜色的泡泡相连,我们就说这两个泡泡相连。

为了方便描述,我们定义发射点的坐标为(0,0),每次Fish会在发射点以某个给定角度发射某种颜色的泡泡。 如果泡泡撞到墙壁或者其他泡泡(即在某个时间第一次与墙壁或者其他泡泡相切),这个泡泡就会停住。 如果这个泡泡与超过一个泡泡相连,那么这些泡泡就会消失,而Fish就会得到消失泡泡数量的平方的分数值。

请注意,初始时如果有超过两个泡泡相连,这些泡泡并不会消失。

现在已知初始泡泡的情况和每次发射泡泡的颜色和角度(相对于+x轴逆时针方向),请你给出最终的总得分。

注意,在上一次发射出去的泡泡停止之前,Fish不能够继续发射泡泡。

【输入】

输入的第一行有两个实数W,H,表示游戏区域的边界坐标,精确到小数点后六位。

接下来一行有一个整数n,表示初始泡泡的个数。

接下来n行,第i行首先是两个浮点数xi和yi,表示第i个泡泡的圆心坐标,精确到小数点后八位,然后是一个整数ci,表示第i个泡泡的颜色。

接下来一行有一个整数q,表示发射的泡泡的个数。

最后q行,第i行首先是一个浮点数αi,精确到小数点后两位,表示第i次发射的泡泡的角度,然后是一个整数ci,表示第i次发射的泡泡的颜色。

数据保证刚开始所有的泡泡均在区域内!

数据保证泡泡刚发射的位置永远不会停放有泡泡!

由于泡泡会在海水中浮动(以及计算机浮点的精度误差),我们认为当(xa−xb)^2+(ya−yb)^2≤(2×1)^2+1e-6成立时,泡泡a和泡泡b相切!

数据保证初始时不存在相交的泡泡!

【输出】

输出只有一行,这一行只有一个整数,代表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

【数据范围】

对于30%的数据,1≤n≤10,1≤q≤10。

另有50%的数据,1≤n≤1000,1≤q≤1000。

剩下20%的数据,1≤n≤10^5,1≤q≤10。

对于所有的数据,有0<α<180,0<W,H≤1000,1≤ci≤100。

【题解】

一道计算几何模拟题,虽然很恶心但没什么思维难度,但第一次还是写萎了……

首先预处理出初始时圆的相切情况,O(n^2)的做法很容易想到,但与一个圆相切的等圆最多有6个,显然这么做大部分判断是没用的。为了把相邻的圆凑到一起判断,我们把所有圆按横坐标排序后,用扫描线维护与当前碰到的圆横坐标之差不超过2的圆的纵坐标,二分判断一下,就能做到最坏O(nlogn)的预处理了(其实达不到O(nlogn),因为扫描线上维护的圆个数和H有关)。

处理好后发现接下来O(nq)处理即可,每次算出圆最终停留的位置,bfs判断一下相邻且颜色相同的圆,然后标记消除并计算分数即可(注意分数要开long long)。

【代码】

以后代码量大的题都要想清楚了再写啊,感觉写萎一次好伤啊sad

http://paste.ubuntu.com/11711763/

评论

© OI技术宅 | Powered by LOFTER