2013-11-09 19:57:28Morris
[ZJ][D&C] d847 2D rank finding problem
內容 ：
二度空間上的排名計算問題(2D rank finding problem)：給定二度平面空間(2D)上的點A = (a1,a2)與點B = (b1,b2)，其大小關係定義為若A > B 若且唯若 a1> b1 且 a2 > b2 ;亦即A點在B點的右上方。如下圖中，B >A, C>A, D>A, D>C, D> B。值得注意的是，並非任意兩點均可以決定大小關係，如下圖中的點A與點E，點D與點E等，無法決定這兩點的大小關係故為無法比較(incomparable)。給定N個點(x1,y1), (x2,y2), …, (xn,yn)，定義某一個點的排名(rank) 為所給的點集合中，比該點小的點的個數。
如上圖中，rank(A)= 0, rank(B) = 1, rank(C) = 1, rank(D) = 3, rank(E) = 0。
設計一個程式，從檔案讀取點的名稱與座標，計算出在所給定的集合中，所有點的排名值。
輸入說明 ：
有多組測試資料
每組的第一行有一個數字N ( 1 ≦ N ≦ 10000 )
接下來會有N行，每行上會有兩個數字 x y ( 1 ≦ x , y ≦ 1000 )
輸出說明 ：
請按照輸入的順序，求出對於 ( x , y ) 有多少個點 ( a , b )
在它的左下方 a < x , b < y
範例輸入 ：
5 961 404 640 145 983 888 539 71 437 532
範例輸出 ：
2 1 4 0 0
提示 ：
Segment tree(ST)
Binary indexed tree(BIT)
出處 ：
ST | BIT | 98台中區程式題
(管理：morris1028)
以前的確是用 ST 和 BIT 去解決這個問題。
現在回過頭來思考一下如何使用 D&C 來對付這一道題。
首先，思考對於 x 軸的劃分，類似於 merge sort。
當區間合併時，排序對照 y 軸大小排序，因此合併時可以得到比它 y 值還小的個數。
但是由於要對 x 軸劃分，進行 D&C 前，先使用預排序解決。
因為會有相同 x 座標的問題，為了防止計算上的疑慮(因為合併時無法保證 x 軸的單調)
因此再對 y 軸做降排序。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
int x, y, idx, r;
Pt(int a=0, int b=0, int c=0):
x(a), y(b), idx(c), r(0) {}
bool operator<(const Pt &a) const {
if(x != a.x)
return x < a.x;
return y > a.y;
}
};
Pt D[10005], X[10005];
void DCmerge(int l, int m, int r) {
int idx1 = l, idx2 = m+1, top = 0;
int d = 0, i;
while(idx1 <= m && idx2 <= r) {
if(D[idx1].y < D[idx2].y)
X[top++] = D[idx1++], d++;
else
X[top++] = D[idx2++], X[top-1].r += d;
}
while(idx1 <= m) X[top++] = D[idx1++];
while(idx2 <= r) X[top++] = D[idx2++], X[top-1].r += d;
for(i = 0; i < top; i++)
D[l++] = X[i];
}
void DC(int l, int r) {
if(l >= r) return ;
int m = (l+r)/2;
DC(l, m);
DC(m+1, r);
DCmerge(l, m, r);
}
int main() {
int n, i, j;
int x, y;
int output[10005];
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++) {
scanf("%d %d", &x, &y);
D[i] = Pt(x, y, i);
}
sort(D, D+n);
DC(0, n-1);
for(i = 0; i < n; i++)
output[D[i].idx] = D[i].r;
for(i = 0; i < n; i++)
printf("%d\n", output[i]);
}
return 0;
}
以前的確是用 ST 和 BIT 去解決這個問題。
現在回過頭來思考一下如何使用 D&C 來對付這一道題。
首先，思考對於 x 軸的劃分，類似於 merge sort。
當區間合併時，排序對照 y 軸大小排序，因此合併時可以得到比它 y 值還小的個數。
但是由於要對 x 軸劃分，進行 D&C 前，先使用預排序解決。
因為會有相同 x 座標的問題，為了防止計算上的疑慮(因為合併時無法保證 x 軸的單調)
因此再對 y 軸做降排序。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
int x, y, idx, r;
Pt(int a=0, int b=0, int c=0):
x(a), y(b), idx(c), r(0) {}
bool operator<(const Pt &a) const {
if(x != a.x)
return x < a.x;
return y > a.y;
}
};
Pt D[10005], X[10005];
void DCmerge(int l, int m, int r) {
int idx1 = l, idx2 = m+1, top = 0;
int d = 0, i;
while(idx1 <= m && idx2 <= r) {
if(D[idx1].y < D[idx2].y)
X[top++] = D[idx1++], d++;
else
X[top++] = D[idx2++], X[top-1].r += d;
}
while(idx1 <= m) X[top++] = D[idx1++];
while(idx2 <= r) X[top++] = D[idx2++], X[top-1].r += d;
for(i = 0; i < top; i++)
D[l++] = X[i];
}
void DC(int l, int r) {
if(l >= r) return ;
int m = (l+r)/2;
DC(l, m);
DC(m+1, r);
DCmerge(l, m, r);
}
int main() {
int n, i, j;
int x, y;
int output[10005];
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++) {
scanf("%d %d", &x, &y);
D[i] = Pt(x, y, i);
}
sort(D, D+n);
DC(0, n-1);
for(i = 0; i < n; i++)
output[D[i].idx] = D[i].r;
for(i = 0; i < n; i++)
printf("%d\n", output[i]);
}
return 0;
}
(悄悄話)
2020-10-21 13:10:58