ĐỀ TÀI: BÀI TOÁN CẶP ĐIỂM GẦN NHẤT I. Mở đầu §a sè c¸c thuËt to¸n ®Òu tËp trung xö lÝ trªn v¨n b¶n (xö lÝ trªn x©u) vµ c¸c con sè, chóng ®îc thiÕt kÕ vµ xö lÝ s½n trong phÇn lín c¸c bµi to¸n lËp tr×nh. §èi víi c¸c bµi to¸n h×nh häc th× ®ßi hái kh¸c h¼n, ngêi lËp tr×nh ph¶i cã sù tÝnh to¸n tØ mØ c¸c c«ng thøc vÒ h×nh häc tríc khi ®i vµo lËp tr×nh. Khi lµm c¸c bµi tËp vÒ h×nh häc th- êng ph¶i ®ßi hái sù c«ng phu lËp tr×nh h¬n c¸c bµi tËp kh¸c, nhÊt lµ viÖc thiÕt lËp c¸c c«ng thøc th× bµi lËp tr×nh míi cã hiÖu qu¶. 1. §èi tîng h×nh häc c¬ b¶n Trong c¸c bµi to¸n Tin häc thuéc lo¹i h×nh häc cã 3 ®èi t- îng c¬ b¶n lµ: §iÓm, §o¹n th¼ng vµ §a gi¸c. §iÓm: §îc xÐt b»ng mét cÆp sè nguyªn lµ täa ®é cña ®iÓm ®ã trong hÖ trôc täa ®é Descartes thêng dïng. §o¹n th¼ng: Lµ mét cÆp ®iÓm ®îc nèi víi nhau mét phÇn cña ®êng th¼ng. §a gi¸c: Lµ mét d·y c¸c ®iÓm víi hai ®iÓm liªn tiÕp ®îc nèi bëi mét ®o¹n th¼ng, vµ ®iÓm ®Çu ®îc nèi víi ®iÓm cuèi t¹o thµnh mét h×nh gÊp khóc khÐp kÝn. 2. D÷ liÖu lu tr÷ c¸c ®èi tîng h×nh häc c¬ b¶n Lµm viÖc víi c¸c ®èi tîng h×nh häc chóng ta cÇn quyÕt ®Þnh thÓ hiÖn chóng nh thÕ nµo? Th«ng thêng ta dïng mét m¶ng ®Ó biÓu diÔn mét ®a gi¸c, dï r»ng mét 1 sè trêng hîp kh¸c chóng ta cã thÓ dïng danh s¸ch liªn kÕt hay c¸c kiÓu kh¸c. §èi tîng chóng ta thêng xuyªn ph¶i lµm viÖc víi h×nh häc lµ täa ®é, do ®ã viÖc lu tr÷ to¹ ®é cña c¸c ®iÓm lµ phæ biÕn trong c¸c bµi to¸n lËp tr×nh vÒ h×nh häc. II. Nội dung 1. Phát biểu bài toán Bài toán: Cho N điểm trên mặt mẳng tọa độ, tìm khoảng cách ngắn nhất giữa hai điểm bất kỳ. 2. Thuật toán Bài toán này ta có thể dễ dàng thực hiện thuật toán bruteforce , ta xét tất cả các cặp điểm và chọn cặp có khoảng cách ngắn nhất giữa chúng. Thuật toán có độ phức tạp O( n2 ). Ta có một số thuật toán tốt hơn như sau: 2.1.Thuật toán chia để trị a. Ý tưởng thuật toán Thuật toán chia để trị giải quyết bài toán này thực hiện như sau:  Sắp xếp các điểm đã cho theo thứ tự từ trái sang phải. Chia tập điểm thành hai tập.  Thực hiện thao tác đệ quy, tìm cặp điểm gần nhất trong hai tập con, trả lại giá trị là khoảng cách ngắn nhất trong tập đó.  Gọi δ là khoảng cách ngắn nhất, trong hai khoảng cách ngắn nhất trong hai tập con. Ta chỉ quan tâm tới các cặp có khoảng cách nhỏ hơn δ . 2  Xét trong “cửa sổ” độ rộng 2 δ, sắp xếp tất cả các điểm trong cửa sổ đó theo thứ tự tăng dần chiều tọa độ y .  Nhận xét: vì khoảng cách giữa mỗi cặp điểm bất kỳ trên hai tập không nhỏ hơn δ nên với mỗi một điểm trên “cửa sổ”, có không quá 3 điểm mỗi bên có khoảng cách tọa độ y nhỏ hơn hoặc bằng δ so với điểm đó. Do vậy, với mỗi điểm, ta chỉ cần xét (ghép cặp) không quá 6 điểm để có thể tìm ra cặp điểm có khoảng cách Euclid nhỏ hơn δ . b. Cài đặt Sử dụng đệ quy quay lui để cài đặt thuật toán. Với mỗi đoạn:  Nếu độ dài đoạn n ≤ 3, ta tính toán bruteforce để tìm cặp điểm gần nhất.  Nếu độ dài n ≥ 3 ta chia đôi tập, đệ quy quay lui để tính khoảng cách gần nhất trong hai tập con, chọn giá trị bé nhất trong hai khoảng cách.  Dùng mảng strip để trộn hai phía theo thứ tự tăng dần y , lọc lấy những phần tử có chênh lệch y nhỏ hơn giá trị min đang có. (d ). Chú ý sau khi thực hiện, ta thực hiện sắp xếp trộn hai phía của đoạn theo 3 thứ tự tăng dần y luôn, độ phức tạp O(n), không sử dụng thuật toán sắp xếp khác.  Với các phần tử trong cửa sổ, với mỗi điểm, xét các điểm lân cận (sau khi đã sắp xếp) có chênh lệch y nhỏ hơn d . (số phần tử này ≤ 6 ¿ 4 Dưới đây là chương trình cài đặt tính cặp điểm gần nhấttheo thuật toán chia để trị: Input:  Dòng đầu tiên là số N – số lượng điểm( n≤ 2.10 5)  N dòng tiếp theo, mỗi dòng chứa tọa độ một điểm theo thứ tự. Output: Khoảng cách nhỏ nhất cần tìm, chính xác 5 chữ số phần thập phân. CLOSESTPAIR.INP CLOSESTPAIR.OUT 3 1.00000 1 1 2 2 2 1 Chương trình: #include #define sz(x) int(x.size()) #define MIN(x,y) if (x < y) x = y #define PB push_back #define mp make_pair #define Task "closestpair" #define maxn 200002 #define MOD 1000000007 #define remain(x) if (x > MOD) x -= MOD #define pii pair #define X first #define Y second using namespace std; pii a[maxn], strip[maxn]; double ans = 1e10; double Distance(pii P1, pii P2) { 5 double XX = P1.X - P2.X; double YY = P1.Y - P2.Y; return sqrt(XX*XX + YY*YY); } double bruteForce(pii P[], int n) { double kmin = FLT_MAX; for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) kmin = min(kmin, Distance(P[i], P[j])); return kmin; } bool compareY(pii p1, pii p2) { return (p1.Y < p2.Y || (p1.Y == p2.Y && p1.X < p2.X)); } double stripClosest(pii strip[], int n, double d) { double kmin = d; for (int i = 0; i < n; ++i) for (int j = i+1; j < n && (strip[j].Y - strip[i].Y) < kmin; j++) kmin = min(Distance(strip[i],strip[j]), kmin); return kmin; } double Calc(pii P[], int n) { if (n <= 3) { sort (P, P+n, compareY); return bruteForce(P, n); } int mid = n/2; pii midPoint = P[mid]; double dl = Calc(P, mid); double dr = Calc(P + mid, n-mid); double d = min(dl, dr); 6 int ccount = 0; merge(P, P+mid, P+mid, P+n, strip,compareY); for (int i = 0; i < n; i++) { P[i] = strip[i]; if (abs(strip[i].X - midPoint.X) < d) strip[ccount++] = strip[i]; } return min(d, stripClosest(strip, ccount, d)); } double Closest(pii a[], int n) { sort(a, a+n); return Calc(a,n); } int main() { ios_base::sync_with_stdio(0); freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i].X >> a[i].Y; printf("%0.5f", Closest(a,n)); return 0; } c. Đánh giá Việc tính trong cửa sổ 2 δ và sắp xếp trộn với một đoạn độ dài n (không tính hai đoạn con) có độ phức tạp O(n). Số lần lặp thủ tục tính có lời gọi không quá log 2 n lần nên tổng độ phức tạp thuật toán là O(nlgn). 7 2.2.Thuật toán sweep line a. Ý tưởng thuật toán.  Sắp xếp tọa độ các điểm theo chiều x .  Xét từng điểm từ trái qua phải. Giả sử ta đang xét tới điểm p và giá trị nhỏ nhất giữa hai điểm trong các điểm bên trái plà d . Rõ ràng ta chỉ giữ lại những điểm có khoảng cách tới tọa độ x của p là δ< d (hình trái)  Với điểm p ta chỉ cần xét những điểm có chênh lệch cả x và y so với p không quá d . (hình bên phải). Dễ thấy, vì d là khoảng cách ngắn nhất giữa 2 điểm trong tập điểm bên trái đã xét nên chắc chắn có không quá 4 điểm như vậy. b. Cài đặt Sử dụng thêm cấu trúc set để lưu trữ các phần tử trong “vệt quét” hay nói cách khác là các phần tử có tọa độ x có khoảng cách tới tọa độ x của p đang xét nhỏ hơn giá trị d hiện tại. Đồng thời dễ ràng thêm, xóa và tìm kiếm các phần tử trong phạm vi p . y −d → p . y+ d . 8 Dưới đây là chương trình cài đặt tính cặp điểm gần nhấttheo thuật toán sweepline: #include #define sz(x) int(x.size()) #define MIN(x,y) if (x < y) x = y #define PB push_back #define mp make_pair #define F first #define S second #define Task "closestpair" #define maxn 200002 #define MOD 1000000007 #define remain(x) if (x > MOD) x -= MOD #define pii pair #define Y first #define X second using namespace std; pii a[maxn]; set S; double Distance(pii P1, pii P2) { double XX = P1.X - P2.X; double YY = P1.Y - P2.Y; return sqrt(XX*XX + YY*YY); } bool compareX(pii p1, pii p2) { return (p1.X < p2.X || (p1.X == p2.X && p1.Y < p2.Y)); } double Closest(pii a[], int n) 9