本文共 3426 字，大约阅读时间需要 11 分钟。
题意：数组二维空间内的点，求最近的俩个点的距离.
根据x排序,求左部分的最近距离,右部分最近距离,然后以中点,当前距离为半径,计算所有的点距离.
#include #include #include #include #include #include #include #include #include #include #include #include #include"math.h"#include "stdio.h"namespace cc{ using std::cout; using std::endl; using std::cin; using std::map; using std::vector; using std::string; using std::sort; using std::priority_queue; using std::greater; using std::vector; using std::swap; using std::stack; using std::bitset; class Node { public: double x; double y; Node() {}; Node(double x, double y) :x(x), y(y) {}; }; constexpr int N = 10000; Node a[N + 1]; bool cmp(Node& a, Node& b) { return a.x < b.x; } double dist(Node a, Node b) { return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); } double minDist(int l, int r) { if (l > r) return 40004; int mid = (l + r) / 2; int s = mid, e = mid; double d = std::min(minDist(l, mid - 1), minDist(mid + 1, r)); while (s >= l && d > a[mid].x - a[s].x) s--; while (e <= r && d > a[e].x- a[mid].x) e++; for (int i = s + 1;i < e;i++) { for (int j = i + 1;j < e;j++) { d = std::min(dist(a[i], a[j]), d); } } return d; } void solve() { double s, e; int n; while (cin >> n && n) { for (int i = 0;i < n;i++) { cin >> s >> e; Node node(s, e); a[i] = node; } sort(a, a + n, cmp); double d = minDist(0,n-1); if (d >= 10000) { cout << "INFINITY" << endl; } else { printf("%.4lf\n",d); } } }};int main(){#ifndef ONLINE_JUDGE freopen("d://1.text", "r", stdin);#endif // !ONLINE_JUDGE cc::solve(); return 0;}
另外,这个题裸奔也行的
#include #include #include #include #include #include #include #include #include #include #include #include #include"math.h"#include "stdio.h"namespace cc{ using std::cout; using std::endl; using std::cin; using std::map; using std::vector; using std::string; using std::sort; using std::priority_queue; using std::greater; using std::vector; using std::swap; using std::stack; using std::bitset; class Node { public: double x; double y; Node() {}; Node(double x, double y) :x(x), y(y) {}; }; constexpr int N = 10000; Node a[N + 1]; bool cmp(Node& a, Node& b) { return a.x < b.x; } double dist(Node a, Node b) { return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); } double minDist(int l, int r) { if (l > r) return 40004; int mid = (l + r) / 2; int s = mid, e = mid; double d = std::min(minDist(l, mid - 1), minDist(mid + 1, r)); while (s >= l && d > a[mid].x - a[s].x) s--; while (e <= r && d > a[e].x- a[mid].x) e++; for (int i = s + 1;i < e;i++) { for (int j = i + 1;j < e;j++) { d = std::min(dist(a[i], a[j]), d); } } return d; } void solve() { double s, e; int n; while (cin >> n && n) { for (int i = 0;i < n;i++) { cin >> s >> e; Node node(s, e); a[i] = node; } sort(a, a + n, cmp); double d = 400000; for (int i = 0;i < n;i++) { for (int j = i + 1;j < n;j++) { d = std::min(dist(a[i],a[j]),d); } } if (d >= 10000) { cout << "INFINITY" << endl; } else { printf("%.4lf\n",d); } } }};int main(){#ifndef ONLINE_JUDGE freopen("d://1.text", "r", stdin);#endif // !ONLINE_JUDGE cc::solve(); return 0;}
转载于:https://www.cnblogs.com/shuiyonglewodezzzzz/p/10258327.html