hd1007

简介:

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

struct node
{
double x,y;
}point[100000];
int n;

bool hAlignLess(node p1,node p2)
{
if(p1.x != p2.x) return p1.x < p2.x;
else return p1.y < p2.y;
}

double getDist(node p1, node p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

double getMin(double a, double b)
{ 
return a<b?a:b;
}

double solve(int l,int r)
{
    if(l == r)
       return 1000000000;
    if(l == r - 1)
       return getDist(point[l],point[r]);
    if(l == r - 2)
       return getMin(getMin(getDist(point[l],point[l+1]),getDist(point[l+1],point[l+2])),getDist(point[l],point[l+2]));
    int i,j,mid = (l+r) >> 1;
    double curmin = getMin(solve(l,mid),solve(mid+1,r));
    for(i=l;i<=r;i++)
       for(j=i+1;j<=i+5 && j<=r;j++)
       {
        curmin = getMin(curmin,getDist(point[i],point[j]));
       }
    return curmin;
}

int main() {
    int i;
    while(scanf("%d",&n)!=EOF && n){
       for(i = 0; i < n; i++){
            scanf("%lf %lf",&point[i].x,&point[i].y);
       }
       sort(point,point+n,hAlignLess);
       double ans = solve(0,n-1);
       printf("%.2lf\n",ans/2);
    }
    return 0;
}

相关文章
|
3月前
|
存储 Linux Android开发
Ext3、Ext4、FAT、FAT32、NTFS、exFAT、Sparse、Raw
Ext3、Ext4、FAT、FAT32、NTFS、exFAT、Sparse、Raw
105 0
程序人生 - 戴森 Dyson HD01 和 HD03 区别?
程序人生 - 戴森 Dyson HD01 和 HD03 区别?
170 0
程序人生 - 戴森 Dyson HD01 和 HD03 区别?
|
Linux
什么是Linux的LVM:PE, PV, VG, LV 的意义是?
什么是Linux的LVM:PE, PV, VG, LV 的意义是?
795 0
什么是Linux的LVM:PE, PV, VG, LV 的意义是?
|
SQL 移动开发 C++
PCIe-SSD卡下的xfs vs ext4对比fileio及TpmC测试
PCIe-SSD卡下的xfs vs ext4对比fileio及TpmC测试
162 0