2 0 0 1 1 2 1 1 1 1 3 -1.5 0 0 0 0 1.5 0
0.71 0.00 0.75
题目大意：
给你很多点，问你最近点的距离一半是多少。
解题思路：
最近点对，参照：http://blog.csdn.net/hellobabygogo3/article/details/8042650
解题代码：（参照它的思路，感觉我的代码比较简洁一些）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=110000;
struct point{
double x,y;
double getdis(point p){
return sqrt( (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y) );
}
friend bool operator < (point a,point b){
if(a.x!=b.x) return a.x<b.x;
else return a.y<b.y;
}
}p[maxn];
int n;
bool cmp(point a,point b){
if(a.y!=b.y) return a.y<b.y;
else return a.x<b.x;
}
double getmin(int l,int r){
if(r-l==0) return 1e18;
if(r-l==1) return p[l].getdis(p[r]);
int mid=(l+r)/2;
double ans=min( getmin(l,mid),getmin(mid+1,r) );
vector <point> v;
for(int i=l;i<r;i++){
if( fabs(p[i].x-p[mid].x) < ans ) v.push_back(p[i]);
}
sort(v.begin(),v.end(),cmp);
for(int i=0;i<v.size();i++){
for(int j=i+1;j<v.size();j++){
if(v[j].y-v[i].y>=ans) break;
double tmp=v[j].getdis(v[i]);
if(tmp<ans) ans=tmp;
}
}
return ans;
}
void solve(){
double ans=1e18;
sort(p,p+n);
printf("%.2lf\n",getmin(0,n-1)/2.0);
}
int main(){
while(scanf("%d",&n)!=EOF && n>0){
for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
solve();
}
return 0;
}
HDU 1007 Quoit Design （分治）,布布扣,bubuko.com
原文：http://blog.csdn.net/a1061747415/article/details/28441285