每日一题——第六十五题

题目：平面上有n个点，求所有各点之间的最长距离。

#include <stdio.h>  
#include <stdlib.h>  
#include <float.h> // For DBL_MAX  typedef struct {  double x, y;  
} Point;  // 用于比较两个点的x坐标，如果x相同则比较y  
int comparePoints(const void *a, const void *b) {  Point *p1 = (Point *)a;  Point *p2 = (Point *)b;  if (p1->x != p2->x) {  return (p1->x < p2->x) ? -1 : 1;//返回-1表示 p1->x在p2->x之前，即p1->x < p2->x } else {  return (p1->y < p2->y) ? -1 : 1;//同理  }  
}  // 计算两点之间的距离  
double distance(Point p1, Point p2) {  double dx = p1.x - p2.x;  double dy = p1.y - p2.y;  return sqrt(dx * dx + dy * dy);  
}  // 求解最长距离  
double longestDistance(Point points[], int n) {  if (n <= 1) return 0; // 如果点少于两个，则最长距离为0  // 对点集进行排序  qsort(points, n, sizeof(Point), comparePoints);  double maxDist = 0;  for (int i = 0; i < n - 1; i++) {  // 尝试将点集分为两部分，并计算跨越这两部分的最长距离  for (int j = i + 1; j < n; j++) {  double d = distance(points[i], points[j]);  if (d > maxDist) {  maxDist = d;  }  // 剪枝：如果当前点与最后一个点形成的距离已经小于当前最大距离，则无需继续向后比较  if (d < maxDist && j != n - 1) {  break;  }  }  }  // 还需要考虑第一个点和最后一个点之间的距离（即最左端点和最右端点）  double lastToFirst = distance(points[0], points[n - 1]);  if (lastToFirst > maxDist) {  maxDist = lastToFirst;  }  return maxDist;  
}  int main() {  Point points[] = {{1, 2}, {2, 3}, {4, 5}, {7, 8}, {0, 0}};  int n = sizeof(points) / sizeof(points[0]);  double longest = longestDistance(points, n);  printf("最长距离为: %.2f\n", longest);  return 0;  
}