﻿二维最近点对-Ocrosoft

# 二维最近点对

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,v,b) for(int a=v;a<b;a++)
#define  repe(a,v,b) for(int a=v;a<=b;a++)
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 300000+ 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
using namespace std;
struct Point
{
Point(){this->x=this->y=0;}
Point(double x,double y){this->x=x;this->y=y;}
double x,y;
};
double dis(Point a, Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
vector<Point> v;
double CP(int left,int right)
{
double d=INF;
if(left==right)return d;
int mid=(left+right)>>1;//已排序，mid为中位点序号
double d1=CP(left,mid);//分治
double d2=CP(mid+1,right);
d=min(d1,d2);//两个区间的最近点距离
int i,j,k=0;
vector<int> tmp;
for(i=left;i<right;i++)
if(abs(v[mid].x-v[i].x)<=d)
tmp.push_back(i);//所有与中位点X坐标差小于等于最小距离的点的序号
/*y坐标排序*/
sort(tmp.begin(),tmp.end(),[v](const int a,const int b){return v[a].y<v[b].y;});
for(i=0;i<tmp.size();i++)
for(j=i+1;j<tmp.size()&&v[tmp[j]].y-v[tmp[i]].y<d;j++)
d=min(dis(v[tmp[i]],v[tmp[j]]),d);//取最小距离
return d;
}
int main()
{
int n;cin>>n;
while(n--)
{
double x,y;
cin>>x>>y;
Point p(x,y);
v.push_back(p);
}
/*O(N^2)*/
double minn=INF;
for(int i=0;i<v.size();i++)
for(int j=i+1;j<v.size();j++)
minn=min(minn,dis(v[i],v[j]));
cout<<minn<<endl;
/*O(N*logN)*/
sort(v.begin(),v.end(),[v](Point a,Point b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;});
cout<<CP(0,v.size())<<endl;
return 0;
}
```