#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
double x;
double y;
}pttype;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const long maxsize = 100000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long arr[maxsize];
long arr1;
pttype pt[maxsize];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int sortcmp(const void *a, const void *b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if (((pttype*)a)->x < ((pttype*)b)->x)
return -1;
else
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double dis(pttype a,pttype b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double getMin(double a, double b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(a<b)
return a;
else
return b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int arrcmp(const void *a, const void *b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if (pt[*(int*)a].y < pt[*(int*)b].y)
return -1;
else
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double shortest(long left,long right)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(right-left == 1)
return dis(pt[left],pt[right]);
if(right-left == 2)
return getMin(getMin(dis(pt[left], pt[left+1]), dis(pt[left], pt[right])), dis(pt[left+1], pt[right]));
long i,j,mid = (left + right) >> 1;
double curmin = getMin(shortest(left,mid),shortest(mid +1 ,right));
arr1 = 0;
for (i = mid; i >= left && pt[mid+1].x - pt[i].x <= curmin; i --)
arr[arr1++] = i;
for (i = mid + 1; i <= right && pt[i].x - pt[mid].x <= curmin; i ++)
arr[arr1++] = i;
qsort(arr, arr1, sizeof(arr[0]), arrcmp);
for (i = 0; i < arr1; i ++)
for (j = i + 1; j < arr1 && pt[arr[j]].y - pt[arr[i]].y <= curmin; j ++)
curmin = getMin(curmin, dis(pt[arr[i]], pt[arr[j]]));
return curmin;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
long n,i;
while(1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d",&n);
if(n == 0)
break;
for(i = 0;i < n;i++)
scanf("%lf%lf",&pt[i].x,&pt[i].y);
qsort(pt,n,sizeof(pt[0]),sortcmp);
printf("%.2lf\n",shortest(0,n-1)/2);
}
return 0;
}