Figure 1: Two Nuclear Power Plants. Houses at (81, 49) and (77,33) are at high risk from both the plants.
We will describe the entire scenario in a flat land, so two-dimensional Cartesian coordinate system is used to denote each location. Letsassume that the coordinate of the two nuclear power plants are (ax, ay) and (bx, by). Houses that are located within distance R1 (inclusive) of the power plant at (ax, ay) are under high risk of radiation. Similarly, houses that are located within distance R2 (inclusive) of the power plant at (bx, by) are under high risk of radiation. So the authorities of power plant 1 and power plant 2 distribute special protective equipments to the houses that are within radius (inclusive) R1 and R2 of the respective power plants. As a result each of the houses that are endangered by both the plants actually receive two sets of equipments to protect their house, however only one set is enough for full protection. Houses that are outside the high-risk area are under low risk of radiation but they do not receive any protective equipment due to budget constraints. However, each owner of the houses that have two sets of protective equipments gives away one set of equipment to the owner of a house that has none. Still, some houses in the low-risk area remain un-protected. Given the location of the houses and the values of ax, ay, bx, by and possible values of R1 and R2 your job is to find out the number of houses that are without protective equipments for each pair of values of R1 and R2.
Input
The input file contains at most 3 test cases. The description of each test case is given below:
A test case starts with a line containing a positive integer N (0 < N ≤ 200000) that denotes the number of houses that are under either low risk or high risk of radiation. Each of the next N lines contains two integers xi, yi (0 ≤ xi, yi ≤ 20000) that denotes the coordinate of the i-thhouse. No two houses are at the same location. The next line contains five integers ax, ay, bx, by and q (0 ≤ ax, ay, bx, by ≤ 20000, 0
A line containing a single zero terminates input. This line should not be processed.OutputFor each test case produce q+1 lines of output. The first line is the serial of output. For each query (given value of R1 and R2) determine how many houses in the low risk region remains without protective equipment. You may consider using faster IO as judge input file is large.Sample Input | Output for Sample Input1195 7527 693 5124 1334 4965 6181 4977 33110 5091 22110 2557 42 97 36 231 2525 250Case 1:22Note: First query in the sample input corresponds to Figure 1.题意：n给定n个点的坐标圆1的坐标 圆2的坐标 询问次数圆1的半径 圆2的半径问：对于每个询问，求出（不在圆上的点 - 在2圆重合 部分的点 ) //注意当答案<0 输出0思路：首先对题意转化，可以看成是求 n - （在圆1上的点）-（在圆2上的点）因为所有点是固定的，所以 （在圆1的点） => DIS( 点，圆心1) <= R1只要求出所有满足上述不等式点的个数即可把所有点按 （到圆心1的距离）小到大排序，存在p1数组中，再把p1中有相同dis的点去重后存在k1数组中，k1.num 就表示 距离<=k1.dis的点有 k1.num个然后二分找到k1.dis <= R1 的最大的k1.num ,就是（在圆1上的点）对圆2上的点相同操作#include#include #include #include #include #include #include #include #include #include #include #include #define inf 2000000 #define N 200200 using namespace std; struct node{ int x,y; int dis; bool operator<(const node& a)const {return a.dis>dis;} }