#P5035. [Jsoi2014]士兵部署

    ID: 4133 传统题 1000ms 256MiB 尝试: 69 已通过: 19 难度: 8 上传者: 标签>难度分类提高+/省选-计算几何Andrew 算法凸多边形二分查询叉积鞋带公式排序与序列处理一维前缀和环形区间拆分CF2400Round3

[Jsoi2014]士兵部署

士兵

题目描述

JYY 的 NN 个士兵位于平面上的 (xi,yi)(x_i,y_i)。

对于一个点,如果从该点出发朝任意方向移动,都能使它与至少一个士兵的距离减少,就称该点可以被守卫。所有这样的点组成可守卫区域。

现在新增一个士兵,有 MM 个候选位置 (ui,vi)(u_i,v_i)。对每个候选位置,分别求把新士兵部署到这里后,可守卫区域的面积。每次询问均基于原来的 NN 个士兵,候选位置之间互不影响。

输入格式

从标准输入读入。第一行两个正整数 N,MN,M。

接下来 NN 行,每行两个整数 xi,yix_i,y_i。

再接下来 MM 行,每行两个整数 ui,viu_i,v_i。

输出格式

向标准输出写出 MM 行,第 ii 行为对应区域的面积,保留一位小数。

样例输入

3 2
0 0
2 -1
1 2
3 1
1 0

样例输出

5.0
2.5

数据范围

N,M≤105N,M\le10^5,全部坐标均在 [−108,108][-10^8,10^8] 内。给定的士兵位置和候选位置互不相同。