#P3046. lagoon

    ID: 2178 传统题 1000ms 512MiB 尝试: 65 已通过: 34 难度: 5 上传者: 标签>CF1800普及+/提高-普通并查集无向连通分量路径压缩按大小合并Poetize8

lagoon

题目描述

忘川沧月的小水塘的水面是一片由以下两种图形组成的图案:

这两种图形都由一个边长为 22 的正方形和两个半径为 1 1 的 1/4 1/4 圆组成,圆心在正方形的两个对角顶点上。

小水塘左上角坐标为 (0,0) (0,0) ,右下角坐标为 (2n,2m) (2n,2m) 。水面上每一个顶点坐标为偶数的 2×2 2\times 2 正方形,都是上面两个图形中的一种。如果我们往水塘中的某个位置倒一桶污水,那么这桶污水会像画图中的油漆桶一样扩散开来,占据一片连续的区域,但是在线条边界处会停止扩散。注意如果倒在了线条上,扩散面积为 0 0 。

如下图所示,就是一个由 4 4 行 4 4 列上述图形组成的、左上角坐标 (0,0) (0,0) 、右下角坐标 (8,8) (8,8) 、某些位置倒了污水的水塘(白色部分为线条边界,线条实际宽度认为是 0 0 ,为了明显、美观,此处加粗显示):

现在给出一个 n n 行 m m 列的由上述两种图形组成的水塘,起初水塘中全部为净水。给定q个往某个坐标上 (x,y) (x,y) 倾倒污水的操作,对于每次操作,请求出在 (x,y) (x,y) 上倾倒的污水最终会扩散多大的面积。

输入格式

第一行两个整数 n n 、m m 。 接下来 n n 行每行 m m 个整数,每个整数是 0 0 或者 1 1 ,中间没有空格隔开。0 0 代表此处是<图lagoon-1>中左侧那个 2×2 2\times 2 的图形,1 1 代表此处是右侧那个图形。例如<图lagoon-2>中的第一行用 0001 表示。

第n+2行是一个整数 q q 。

接下来 q q 行每行两个用空格隔开的整数 x x 、y y ,表示这一次倾倒污水的坐标。

输出格式

对于每个询问,输出此次倾倒的污水最终扩散的面积,四舍五入保留 4 4 位小数。

样例输入 #1

1 2
01
4
0 0
2 0
0 1
0 2

样例输出 #1

0.7854
4.8584
0.0000
4.8584

样例输入 #2

3 1
1
0
1
2
3 1
4 2

样例输出 #2

7.2876
1.5708

数据规模与约定

对于 100%100\% 的数据,1≤n,m,q≤100 1\leq n,m,q\leq 100 ,0≤x≤2n 0\leq x\leq 2n ,0≤y≤2m 0\leq y\leq 2m 。

题目来源

Poetize8