Problem D

Radiation
Time Limit: 2 seconds

 

 

Nuclear power plants (NPP) are a blessing and curse of modern civilization. NPPs have some risks but still it is one of the cheapest ways to produce electricity in the developed world. In this problem we will discuss a situation related to two nuclear plants, which are not far away from each other. 

 

 

We will describe the entire scenario in a flat land, so two-dimensional Cartesian coordinate system is used to denote each location. Lets assume that the coordinate of the two nuclear power plants are (ax, ay) and (bx, by). Houses that are located within distance R₁ (inclusive) of the power plant at (ax, ay) are under high risk of radiation. Similarly, houses that are located within distance R₂ (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 R₁ and R₂ your job is to find out the number of houses that are without protective equipments for each pair of values of R₁ and R₂.

 

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 x_i, y_i (0 ≤ x_i, y_i ≤ 20000) that denotes the coordinate of the i-th house. 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 <q ≤ 20000). The meaning of ax, ay, bx and by are given in the problem statement. Here q denotes the total number of query. Each of the next q lines contains two integers, which denote the values of R₁ and R₂ (0 < R₁, R₂ ≤ 13000) respectively.

 

A line containing a single zero terminates input. This line should not be processed.

 

Output

For each test case produce q+1 lines of output.  The first line is the serial of output. For each query (given value of R₁ and R₂) 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 Input

11 95 75 27 6 93 5 124 13 34 49 65 61 81 49 77 33 110 50 91 22 110 25 57 42 97 36 2 31 25 25 25 0

Case 1: 2 2

Note: First query in the sample input corresponds to Figure 1.

題目頗難理解的，就是將交集的部分，他們會多得到一些保護裝置，將這些保護裝置分給這兩個圈圈外的房子，請問仍沒分到保護裝置的房子個數。
意即 答案 = 兩集合的補集-兩集合的交集

#include <stdio.h>
#include <algorithm>
using namespace std;
int x[200005], y[200005];
int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int bsearch(int v, int l, int r, int *A) {
    static int m;
    while(l <= r) {
        m = (l+r)>>1;
        if(A[m] <= v)
            l = m+1;
        else
            r = m-1;
    }
    while(r >= 0 && A[r] > v) r--;
    return r+1;
}
int main() {
    int n, q, cases = 0;
    int ax, ay, bx, by, i, j, txx, tyy;
    while(scanf("%d", &n) == 1 && n) {
        printf("Case %d:\n", ++cases);
        for(i = 0; i < n; i++) {
            ReadInt(&x[i]);
            ReadInt(&y[i]);
        }
        scanf("%d %d %d %d", &ax, &ay, &bx, &by);
        scanf("%d", &q);
        for(i = 0; i < n; i++) {
            txx = (x[i]-ax)*(x[i]-ax)+(y[i]-ay)*(y[i]-ay);
            tyy = (x[i]-bx)*(x[i]-bx)+(y[i]-by)*(y[i]-by);
            x[i] = txx;
            y[i] = tyy;
        }
        sort(x, x+n);
        sort(y, y+n);
        int r1, r2, ca, cb;
        for(i = 0; i < q; i++) {
            ReadInt(&r1);
            ReadInt(&r2);
            ca = bsearch(r1*r1, 0, n-1, x);
            cb = bsearch(r2*r2, 0, n-1, y);
            r1 = n-ca-cb;
            printf("%d\n", r1 < 0 ? 0 : r1);
        }
    }
    return 0;
}