2012-11-27 08:35:37Morris
[ZJ][離線、BIT、離散化] a580. 輻射擴散
內容 ：
Background
出國比 ACM-ICPC 區預賽，沒有好英文可是不行的。小光這次去泰國合艾打醬油，題目根本看不懂，猶如同 WORLD FINAL 的選手不會應答現場主播，被大陸觀眾講「這傢伙不會英文怎麼做題的？」當然小光沒那麼厲害，不過一只蟲子罷了，誰也沒放在眼裡。
根 據小光解析題目，泰國合艾 Problem D Radiation 在描述兩個核子輻射的影響範圍，每在一個輻射影響範圍內則會獲得一個保護裝置，因此在交集處的房子可以獲得兩個保護裝置。而多的那一份可以交給沒有保護裝 置的房子以防萬一輻射擴散。原題求給定分別兩個的輻射半徑，問有多少房子沒有辦法拿到保護裝置。
當下小光並不是這麼想的，誤以為是要求交集處的房子有多少個。
The Problem
給定平面上 N 個房子的點座標，以及兩個輻射源的點座標。對於 Q 個詢問，每個詢問給定第一與第二輻射源的半徑，求交集處的房子個數(剛好在圓上也是在輻射範圍內)。
輸入說明
：
多筆測資。
每組第一行有一個整數 N，
接下來有 N 行平面的房子整數座標 (x, y)，
以及在 N+2 行給定兩個輻射源 (ax, ay) (bx, by) 以及一個整數 Q 詢問，
接下來有 Q 行詢問 (r1, r2)，r1 是 (ax, ay) 的半徑，r2 是 (bx, by) 的半徑
所有數據數值小於等於 20000 的非負整數。
N = 0 時結束。
輸出說明
：
對每組輸出交集處的點個數，請參照範例輸出。
範例輸入 ：
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
提示
：
出處
：
ACM-ICPC Hatyai 改編
(管理：morris1028)
首先把所有測資讀入，將所有點到兩個點的距離記錄形成 (d1,d2) 對 d1 做升排序，接著將詢問的所有距離 (r1, r2) 也做升排序，接著詢問 (r1i, r2i) 時，先將 d1 <= r1i 的所有數值丟入 BIT，查詢小於等於 r2i 的總個數，使用 BIT 的時候記得要離散化，接著還原成詢問的順序即可。
/**********************************************************************************/
/* Problem: a580 "輻射擴散" from ACM-ICPC Hatyai 改編 */
/* Language: CPP (2513 Bytes) */
/* Result: AC(268ms, 1.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-11-26 08:11:45 */
/**********************************************************************************/
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define maxN 20005
using namespace std;
struct ele {
int x, y, in;
};
int x[maxN], y[maxN], R[maxN];
int C[maxN], out[maxN], lowbit[maxN], size;
ele IN[maxN], P[maxN];
bool cmp(ele a, ele b) {
return a.x < b.x;
}
void modify(int idx) {
while(idx <= size) {
C[idx]++;
idx += lowbit[idx];
}
}
int query(int idx) {
static int sum;
sum = 0;
while(idx) {
sum += C[idx];
idx -= lowbit[idx];
}
return sum;
}
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)
return m+1;
if(A[m] < v)
l = m+1;
else
r = m-1;
}
return l;
}
int main() {
int n, m, q, cases = 0;
int ax, ay, bx, by, i, j;
for(i = 1; i < 20005; i++)
lowbit[i] = i&(-i);
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 < q; i++) {
ReadInt(&IN[i].x);
ReadInt(&IN[i].y);
IN[i].x = IN[i].x*IN[i].x;
IN[i].y = IN[i].y*IN[i].y;
IN[i].in = i;
}
for(i = 0; i < n; i++) {
P[i].x = (x[i]-ax)*(x[i]-ax)+(y[i]-ay)*(y[i]-ay);
P[i].y = (x[i]-bx)*(x[i]-bx)+(y[i]-by)*(y[i]-by);
R[i] = P[i].y;
C[i+1] = 0;
}
sort(IN, IN+q, cmp);
sort(P, P+n, cmp);
sort(R, R+n);
for(i = 1, j = 0; i < n; i++) {
if(R[i] != R[j])
R[++j] = R[i];
}
size = j+1, m = j;
for(i = 0, j = 0; i < q; i++) {
while(j < n && P[j].x <= IN[i].x) {
modify(bsearch(P[j].y, 0, m, R));
j++;
}
out[IN[i].in] = query(bsearch(IN[i].y, 0, m, R));
}
for(i = 0; i < q; i++)
printf("%d\n", out[i]);
}
return 0;
}
首先把所有測資讀入，將所有點到兩個點的距離記錄形成 (d1,d2) 對 d1 做升排序，接著將詢問的所有距離 (r1, r2) 也做升排序，接著詢問 (r1i, r2i) 時，先將 d1 <= r1i 的所有數值丟入 BIT，查詢小於等於 r2i 的總個數，使用 BIT 的時候記得要離散化，接著還原成詢問的順序即可。
/**********************************************************************************/
/* Problem: a580 "輻射擴散" from ACM-ICPC Hatyai 改編 */
/* Language: CPP (2513 Bytes) */
/* Result: AC(268ms, 1.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-11-26 08:11:45 */
/**********************************************************************************/
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define maxN 20005
using namespace std;
struct ele {
int x, y, in;
};
int x[maxN], y[maxN], R[maxN];
int C[maxN], out[maxN], lowbit[maxN], size;
ele IN[maxN], P[maxN];
bool cmp(ele a, ele b) {
return a.x < b.x;
}
void modify(int idx) {
while(idx <= size) {
C[idx]++;
idx += lowbit[idx];
}
}
int query(int idx) {
static int sum;
sum = 0;
while(idx) {
sum += C[idx];
idx -= lowbit[idx];
}
return sum;
}
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)
return m+1;
if(A[m] < v)
l = m+1;
else
r = m-1;
}
return l;
}
int main() {
int n, m, q, cases = 0;
int ax, ay, bx, by, i, j;
for(i = 1; i < 20005; i++)
lowbit[i] = i&(-i);
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 < q; i++) {
ReadInt(&IN[i].x);
ReadInt(&IN[i].y);
IN[i].x = IN[i].x*IN[i].x;
IN[i].y = IN[i].y*IN[i].y;
IN[i].in = i;
}
for(i = 0; i < n; i++) {
P[i].x = (x[i]-ax)*(x[i]-ax)+(y[i]-ay)*(y[i]-ay);
P[i].y = (x[i]-bx)*(x[i]-bx)+(y[i]-by)*(y[i]-by);
R[i] = P[i].y;
C[i+1] = 0;
}
sort(IN, IN+q, cmp);
sort(P, P+n, cmp);
sort(R, R+n);
for(i = 1, j = 0; i < n; i++) {
if(R[i] != R[j])
R[++j] = R[i];
}
size = j+1, m = j;
for(i = 0, j = 0; i < q; i++) {
while(j < n && P[j].x <= IN[i].x) {
modify(bsearch(P[j].y, 0, m, R));
j++;
}
out[IN[i].in] = query(bsearch(IN[i].y, 0, m, R));
}
for(i = 0; i < q; i++)
printf("%d\n", out[i]);
}
return 0;
}