/** 最近点对问题，时间复杂度为O(n*logn*logn) */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const double INF = 1e20; const int N = 100005; struct Point { double x; double y; }point[N]; int n; int tmpt[N]; bool cmpxy(const Point& a, const Point& b) { if(a.x != b.x) return a.x < b.x; return a.y < b.y; } bool cmpy(const int& a, const int& b) { return point[a].y < point[b].y; } double min(double a, double b) { return a < b ? a : b; } double dis(int i, int j) { return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x) + (point[i].y-point[j].y)*(point[i].y-point[j].y)); } double Closest_Pair(int left, int right) { double d = INF; if(left==right) return d; if(left + 1 == right) return dis(left, right); int mid = (left+right)>>1; double d1 = Closest_Pair(left,mid); double d2 = Closest_Pair(mid+1,right); d = min(d1,d2); int i,j,k=0; //分离出宽度为d的区间 for(i = left; i <= right; i++) { if(fabs(point[mid].x-point[i].x) <= d) tmpt[k++] = i; } sort(tmpt,tmpt+k,cmpy); //线性扫描 for(i = 0; i < k; i++) { for(j = i+1; j < k && point[tmpt[j]].y-point[tmpt[i]].y<d; j++) { double d3 = dis(tmpt[i],tmpt[j]); if(d > d3) d = d3; } } return d; } int main() { while(true) { scanf("%d",&n); if(n==0) break; for(int i = 0; i < n; i++) scanf("%lf %lf",&point[i].x,&point[i].y); sort(point,point+n,cmpxy); printf("%.2lf ",Closest_Pair(0,n-1)/2); } return 0; }
#include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <numeric> #include <iomanip> #include <bitset> #include <list> #include <stdexcept> #include <functional> #include <utility> #include <ctime> #define PB push_back #define MP make_pair #define FOR1(n) for(int i=0;i<(n);++i) #define FOR2(l,h) for(int i=(l);i<=(h);++i) #define FOR3(h,l) for(int i=(h);i>=(l);--i) using namespace std; typedef long long LL; typedef pair<int,int> PII; #define PI acos((double)-1) #define E exp(double(1)) #define K 10000+9 const LL INF=1e18; int n; struct Point { LL x,y; }point[K],temp[K]; bool cmpxy(Point a,Point b) { if(a.x!=b.x) return a.x<b.x; return a.y<b.y; } bool cmpy(Point a,Point b) { return a.y<b.y; } LL dist(Point a,Point b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } LL Closest_Pair(int left,int right) { LL d=INF; if(left==right) return d; if(left+1==right) return dist(point[left],point[right]); int mid=(left+right)>>1; LL d1=Closest_Pair(left,mid); LL d2=Closest_Pair(mid+1,right); d=min(d1,d2); int i,j,k=0; for( i=left;i<=right;i++) if((point[i].x-point[mid].x)*(point[i].x-point[mid].x)<=d) temp[k++]=point[i]; sort(temp,temp+k,cmpy); for( i=0;i<k;i++) for( j=i+1;j<k&&(temp[i].y-temp[j].y)*(temp[i].y-temp[j].y)<d;j++) d=min(d,dist(temp[i],temp[j])); return d; } int main() { scanf("%d",&n); for(LL i = 1,x,sum=0; i <=n; i++) { scanf("%lld",&x); sum+=x; point[i].x=i; point[i].y=sum; } sort(point+1,point+n+1,cmpxy); printf("%lld ",Closest_Pair(1,n)); return 0; }
前面两份代码其实并不是真的nlogn级别的，因为在合并时枚举的点的个数并不是6个点，真正的分治法只需枚举六个点就可以。所以前两份代码容易被卡时间！！！这是我在比赛时wa了21发得到的血的教训！！！
#include <iostream> #include <ctime> #include <iterator> #include <functional> #include <algorithm> #include <cmath> #include <vector> using namespace std; struct Point { int x; int y; Point(){} Point(int m_x, int m_y) :x(m_x), y(m_y){} }; /************************************************************************/ /* 函数功能：按点的X坐标排序 */ /************************************************************************/ struct CmpX : public binary_function<bool, Point, Point> { bool operator() (const Point& lhs, const Point& rhs) { return (lhs.x < rhs.x); } }; /************************************************************************/ /* 函数功能：按点的Y坐标排序 */ /************************************************************************/ struct CmpY : public binary_function<bool, Point, Point> { bool operator() (const Point& lhs, const Point& rhs) { return (lhs.y < rhs.y); } }; /************************************************************************/ /* 类功能：产生无重复的随机数 类成员：num 表示要产生的随机数的个数 bound 表示每个随机数的范围[0, bound-1). */ /************************************************************************/ class Random { public: explicit Random(int m_num, int m_bound) :num(m_num), bound(m_bound) { arr = new int[m_bound]; for(int i = 0; i < bound; i++) arr[i] = i; } int* GetResult() { int temp = 0; srand((unsigned)time(0)); for (int i = 0; i < num; i++) { temp = rand() % (bound - i - 1) + i; swap(arr[i], arr[temp]); } return arr; } ~Random() { delete []arr; } private: int *arr; int num; //随机数的个数 int bound; //随机数的范围 }; /************************************************************************/ /* 函数功能：求两点间的距离 */ /************************************************************************/ inline double Distance(const Point& lhs, const Point& rhs) { int x_diff = lhs.x - rhs.x; int y_diff = lhs.y - rhs.y; double res = x_diff * x_diff + y_diff *y_diff; return sqrt(res); } /************************************************************************/ /* 函数功能：求数组中两点间的最短距离 */ /************************************************************************/ double GetShortestDistace(Point arr[], int low, int high) { double result = 0.; if (high - low < 3) //小于等于3个点时 { if (high - low == 1) //2个点时 { double distance = Distance(arr[low], arr[high]); return distance; } else //3个点 { double distance1 = Distance(arr[low], arr[low + 1]); double distance2 = Distance(arr[low], arr[low + 2]); double distance3 = Distance(arr[low + 1], arr[low + 2]); return min(min(distance1, distance2), distance3); } } int middle = (low + high) / 2; double left_distance = GetShortestDistace(arr, low, middle); //求middle左边的最短距离 double right_distance = GetShortestDistace(arr, middle + 1, high); //求middle右边的最短距离 double delta = min(left_distance, right_distance); //中间区域的界限 result = delta; vector<Point> midArea; //存放中间条带区域的点 for (int k = low; k < high; k++) { if(arr[k].x > arr[middle].x - delta && arr[k].x < arr[middle].x + delta) midArea.push_back(arr[k]); } sort(midArea.begin(), midArea.end(), CmpY()); //按Y坐标排序 int size = midArea.size(); for (int i = 0; i < size; i++) { int k = (i + 7) > size ? size : (i+7); //只有选取出7个点(证明过程没看懂) for (int j = i+1; j < k; j++) { if(Distance(midArea.at(i), midArea.at(j)) < result) result = Distance(midArea.at(i), midArea.at(j)); } } return result; } #define N 100 //点的个数 int main() { Point arr[N]; Random random(2*N, 1000); int *result = random.GetResult(); for (int i =0; i < N; i++) arr[i] = Point(result[i], result[i + N]); sort(arr, arr + N, CmpX()); double res = GetShortestDistace(arr, 0, N); cout<<"The shortest distance is:"<<res<<endl; }