当前位置： 面试刷题>> 平面列表 (经典算法题500道)
### 题目描述补充
题目：**平面上的点列表问题**
给定一个包含多个点的平面列表，每个点由其在二维空间中的坐标(x, y)表示。请实现一个算法，完成以下任务之一（或两者都实现，根据面试要求）：
1. **计算最近点对距离**：找到列表中任意两点之间的最短距离。
2. **检测是否存在重合点**：检查列表中是否存在至少两个点坐标完全相同。
**输入**：一个二维数组，其中每个元素是一个包含两个整数的数组，代表一个点的x和y坐标。
**输出**：
- 对于最近点对距离问题，输出最短距离。
- 对于检测重合点问题，如果存在重合点，输出`true`，否则输出`false`。
### 示例代码
#### PHP 示例
```php
function findClosestPairDistance($points) {
if (count($points) < 2) return float('INF');
$minDistance = PHP_INT_MAX;
foreach ($points as $i => $p1) {
foreach ($points as $j => $p2) {
if ($i !== $j) {
$distance = sqrt(pow($p1[0] - $p2[0], 2) + pow($p1[1] - $p2[1], 2));
$minDistance = min($minDistance, $distance);
}
}
}
return $minDistance;
}
function hasDuplicatePoints($points) {
$seen = [];
foreach ($points as $p) {
$key = implode(',', $p);
if (isset($seen[$key])) return true;
$seen[$key] = true;
}
return false;
}
// 示例用法
$points = [[1, 2], [3, 4], [5, 6], [1, 2]]; // 包含一个重合点
echo "Closest Pair Distance: " . findClosestPairDistance($points) . "\n";
echo "Has Duplicate Points: " . (hasDuplicatePoints($points) ? "true" : "false") . "\n";
```
#### Python 示例
```python
import math
def find_closest_pair_distance(points):
if len(points) < 2:
return float('inf')
min_distance = float('inf')
for i in range(len(points)):
for j in range(i + 1, len(points)):
distance = math.sqrt((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2)
min_distance = min(min_distance, distance)
return min_distance
def has_duplicate_points(points):
seen = set()
for point in points:
tuple_point = tuple(point)
if tuple_point in seen:
return True
seen.add(tuple_point)
return False
# 示例用法
points = [(1, 2), (3, 4), (5, 6), (1, 2)] # 包含一个重合点
print("Closest Pair Distance:", find_closest_pair_distance(points))
print("Has Duplicate Points:", has_duplicate_points(points))
```
#### JavaScript 示例
```javascript
function findClosestPairDistance(points) {
if (points.length < 2) return Infinity;
let minDistance = Infinity;
for (let i = 0; i < points.length; i++) {
for (let j = i + 1; j < points.length; j++) {
const distance = Math.sqrt(Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2));
minDistance = Math.min(minDistance, distance);
}
}
return minDistance;
}
function hasDuplicatePoints(points) {
const seen = new Set();
for (const point of points) {
const key = `${point[0]},${point[1]}`;
if (seen.has(key)) return true;
seen.add(key);
}
return false;
}
// 示例用法
const points = [[1, 2], [3, 4], [5, 6], [1, 2]]; // 包含一个重合点
console.log("Closest Pair Distance:", findClosestPairDistance(points));
console.log("Has Duplicate Points:", hasDuplicatePoints(points));
```
在以上示例中，我们分别用PHP、Python和JavaScript实现了计算最近点对距离和检测是否存在重合点的功能。这些代码可以直接在相应的环境中运行以验证其功能。