最近对问题

最近对问题

1000(ms)

10000(kb)

1002 / 5242

Tags: 分治法

设p1=(x1,y1),p2=(x2,y2),…, pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。

多组测试数据，第一行为测试数据组数n（0 输出

每组测试数据输出一行，为该组数据最近点的距离，保留4为小数。 样例输入

2 2 0 0 0 1 3 0 0 1 1 1 0 样例输出

1.0000 1.0000

@浅夏沫若：code

#include
#include
#include
using namespace std;
struct Point
{
 int x;
 int y;
};
int main()
{
 int counter = 0;
 cin >> counter;
 while (counter--)
 {
  int n=0;
  double max = 0.0000;
  double distance = 0.0000;
  Point p[100001];
  cin >> n;
  for (int i = 0; i < n; i++)
  {
   cin >> p[i].x >> p[i].y;
  }
  if (n < 2)
   max = 0;
  else
      max = sqrt((p[0].x - p[1].x)*(p[0].x - p[1].x) + (p[0].y - p[1].y)*(p[0].y - p[1].y));
  for (int i = 0; i < n - 1; i++)
  {
   for (int j = i+1; j < n; j++)
   {
    distance = sqrt((p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y));
    if (distance < max)
     max = distance;
   }
  }
  printf("%.4lfn", max);
 }
 return 0;
}