一維點(diǎn)對(duì)問(wèn)題

描述：一維最近點(diǎn)對(duì)問(wèn)題是指在給定的一維點(diǎn)集中找到距離最近的兩個(gè)點(diǎn)。具體來(lái)說(shuō)，給定一維坐標(biāo)軸上的 n 個(gè)點(diǎn)，要找出其中的兩個(gè)點(diǎn)，使它們的距離最小。
解決辦法：解決這個(gè)問(wèn)題的一種常見(jiàn)方法是使用排序和線性掃描。下面是這種算法的一般步驟：

1. 排序：將點(diǎn)集按照坐標(biāo)從小到大進(jìn)行排序。
2. 初始化最小距離：設(shè)定初始最小距離為正無(wú)窮大。
3. 線性掃描：從左到右遍歷排序后的點(diǎn)集。對(duì)于每個(gè)點(diǎn)，計(jì)算它與其右邊相鄰點(diǎn)的距離，并更新最小距離。
4. 返回最小距離。
   通過(guò)對(duì)點(diǎn)集進(jìn)行排序，可以保證相鄰的點(diǎn)在坐標(biāo)上是接近的，因此只需要線性掃描一次即可找到最小距離的點(diǎn)對(duì)。該算法的時(shí)間復(fù)雜度為 O(n log n)，其中 n 是點(diǎn)集中點(diǎn)的數(shù)量。
   需要注意的是，在實(shí)際實(shí)現(xiàn)中，可以使用歐幾里得距離公式計(jì)算點(diǎn)對(duì)之間的距離，并且在處理邊界情況時(shí)要注意邊界的處理和優(yōu)化，以提高算法的效率。
   總結(jié)來(lái)說(shuō)，一維最近點(diǎn)對(duì)問(wèn)題通過(guò)排序和線性掃描的方法解決。該算法利用了排序后點(diǎn)在坐標(biāo)上的接近性，通過(guò)線性掃描找到最小距離的點(diǎn)對(duì)。
   代碼實(shí)現(xiàn)：
   下面的這段代碼實(shí)現(xiàn)了一個(gè)找出排序后數(shù)組中相鄰元素差值最小的算法。其主要思路如下：
5. 首先定義了一個(gè)全局常量 N，用于表示輸入數(shù)組的最大長(zhǎng)度。同時(shí)定義了一個(gè)數(shù)組 A，用于保存輸入的數(shù)組。
6. 實(shí)現(xiàn)了一個(gè)名為 closet_pot 的遞歸函數(shù)，用于在指定區(qū)間內(nèi)查找相鄰元素差值的最小值.
   首先，判斷區(qū)間的大小。如果區(qū)間只有一個(gè)元素，返回正無(wú)窮表示不存在相鄰元素。
   • 如果區(qū)間只有兩個(gè)元素，直接返回這兩個(gè)元素的差值。
   • 否則，將區(qū)間分為兩個(gè)子區(qū)間，分別遞歸調(diào)用 closet_pot 函數(shù)。
   • 得到左子區(qū)間的最小差值 a，右子區(qū)間的最小差值 b。
   • 然后取 a 和 b 中的較小值作為當(dāng)前區(qū)間的最小差值 Min。
   • 還需要比較當(dāng)前區(qū)間中相鄰兩個(gè)元素的差值，即 A[mid+1] - A[mid]，將其與 Min 比較，更新 Min。
   • 最后，返回 Min 作為當(dāng)前區(qū)間的最小差值。
7. 在 main 函數(shù)中，首先讀取輸入的數(shù)組大小 n。
8. 然后，通過(guò)循環(huán)讀取 n 個(gè)整數(shù)，將它們保存到數(shù)組 A 中。
9. 接下來(lái)，對(duì)數(shù)組 A 進(jìn)行排序，以便找出相鄰元素差值的最小值。
10. 調(diào)用 closet_pot 函數(shù)，并傳入數(shù)組的起始下標(biāo) 0 和結(jié)束下標(biāo) n-1。
11. 輸出最小差值結(jié)果。
12. 最后，使用 system(“pause”) 命令使程序暫停，防止控制臺(tái)窗口關(guān)閉。
    總結(jié)來(lái)說(shuō)，這段代碼通過(guò)遞歸的方式，在排序后的數(shù)組中查找相鄰元素差值的最小值。通過(guò)不斷地將區(qū)間劃分為更小的子區(qū)間，并比較子區(qū)間的最小差值，最終找到整個(gè)數(shù)組中相鄰元素差值的最小值。

#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;int closet_pot(vector<int>& A, int p, int q)
{if (p == q)return INT_MAX;if (p == q - 1)return A[q] - A[p];int mid = (p + q) / 2;int a = closet_pot(A, p, mid);int b = closet_pot(A, mid + 1, q);int Min = min(a, b);Min = min(Min, A[mid + 1] - A[mid]);return Min;
}int main()
{int n;cin >> n;vector<int> A(n);for (int i = 0; i < n; i++)cin >> A[i];sort(A.begin(), A.end());cout << closet_pot(A, 0, n - 1) << endl;return 0;
}

二維點(diǎn)對(duì)問(wèn)題

描述：二維平面上的最近點(diǎn)對(duì)問(wèn)題是指在給定的點(diǎn)集中找到距離最近的兩個(gè)點(diǎn)對(duì)。具體來(lái)說(shuō)，給定平面上的 n 個(gè)點(diǎn)，要找出其中的兩個(gè)點(diǎn)，使它們的距離最小。

解決辦法：解決這個(gè)問(wèn)題的一種常見(jiàn)方法是使用分治算法。下面是這種算法的一般步驟：

1. 排序：按照點(diǎn)的 x 坐標(biāo)進(jìn)行排序，從左到右對(duì)點(diǎn)集進(jìn)行排序。
2. 基本情況處理：如果點(diǎn)集中只有兩個(gè)或三個(gè)點(diǎn)，可以直接計(jì)算它們之間的距離，并找到最小距離的點(diǎn)對(duì)。
3. 分割：將點(diǎn)集平均地分成兩個(gè)子集，左邊和右邊。取中間點(diǎn)將平面分成兩個(gè)部分。
4. 遞歸求解：對(duì)左右兩個(gè)子集遞歸地應(yīng)用最近點(diǎn)對(duì)算法，得到左邊和右邊的最近點(diǎn)對(duì)。
5. 合并：計(jì)算左右兩個(gè)子集的最近點(diǎn)對(duì)的距離。然后，從兩個(gè)子集中選擇距離更小的點(diǎn)對(duì)作為當(dāng)前最近點(diǎn)對(duì)。
6. 跨越邊界：接下來(lái)需要考慮跨越兩個(gè)子集邊界的最近點(diǎn)對(duì)。為了找到這些點(diǎn)對(duì)，以中間點(diǎn)為界限，向左右兩側(cè)延伸一個(gè)距離為當(dāng)前最小距離的區(qū)域。
7. 在跨越邊界區(qū)域內(nèi)，使用簡(jiǎn)單的掃描方法，計(jì)算可能的最近點(diǎn)對(duì)。由于該區(qū)域內(nèi)的點(diǎn)的數(shù)量是有限的，因此復(fù)雜度仍然是線性的。
8. 最后，從左右兩個(gè)子集的最近點(diǎn)對(duì)和跨越邊界區(qū)域的最近點(diǎn)對(duì)中選擇距離最小的點(diǎn)對(duì)作為最終的最近點(diǎn)對(duì)。
   通過(guò)分治策略，最近點(diǎn)對(duì)問(wèn)題的時(shí)間復(fù)雜度可以控制在 O(n log n) 的級(jí)別。
   注意：在實(shí)際實(shí)現(xiàn)中，可以使用歐幾里得距離公式計(jì)算點(diǎn)對(duì)之間的距離，并且在處理邊界情況時(shí)要注意邊界的處理和優(yōu)化，以提高算法的效率。
   總結(jié)：二維平面上的最近點(diǎn)對(duì)問(wèn)題通過(guò)將點(diǎn)集進(jìn)行排序、分割、遞歸求解、合并和跨越邊界的步驟來(lái)解決。該算法利用了分治的思想，通過(guò)逐步縮小問(wèn)題規(guī)模并處理邊界情況，找到平面上距離最近的兩個(gè)點(diǎn)對(duì)。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>using namespace std;struct Point {double x;double y;
};bool compareX(const Point& p1, const Point& p2) {return p1.x < p2.x;
}bool compareY(const Point& p1, const Point& p2) {return p1.y < p2.y;
}double euclideanDistance(const Point& p1, const Point& p2) {double dx = p2.x - p1.x;double dy = p2.y - p1.y;return sqrt(dx * dx + dy * dy);
}double bruteForce(const vector<Point>& points, int start, int end) {double minDist = numeric_limits<double>::max();for (int i = start; i <= end; ++i) {for (int j = i + 1; j <= end; ++j) {double dist = euclideanDistance(points[i], points[j]);minDist = min(minDist, dist);}}return minDist;
}double closestPairUtil(const vector<Point>& points, int start, int end) {if (end - start <= 2) {return bruteForce(points, start, end);}int mid = (start + end) / 2;double midX = points[mid].x;double dl = closestPairUtil(points, start, mid);double dr = closestPairUtil(points, mid + 1, end);double d = min(dl, dr);vector<Point> strip;for (int i = start; i <= end; ++i) {if (abs(points[i].x - midX) < d) {strip.push_back(points[i]);}}sort(strip.begin(), strip.end(), compareY);double stripMin = d;int stripSize = strip.size();for (int i = 0; i < stripSize; ++i) {for (int j = i + 1; j < stripSize && (strip[j].y - strip[i].y) < stripMin; ++j) {double dist = euclideanDistance(strip[i], strip[j]);stripMin = min(stripMin, dist);}}return min(d, stripMin);
}double closestPair(const vector<Point>& points) {int n = points.size();vector<Point> sortedPoints = points;sort(sortedPoints.begin(), sortedPoints.end(), compareX);return closestPairUtil(sortedPoints, 0, n - 1);
}int main() {vector<Point> points = { {2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4} };double minDist = closestPair(points);cout << "最近點(diǎn)對(duì)的距離: " << minDist << endl;return 0;
}