zoj_2107.cpp

Tianjin University Online Judge 的80多道题目 .

//zoj 2107

#include<stdio.h>
#include<cstdlib>
#include<algorithm>
#include<math.h>
#define EPS 1e-6
using namespace std;

struct node{
	double x,y;
}nn[101000],tt[101000],v[101000];

double dist(node a,node b){
	return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int less_x(const void* a,const void* b){
    const node * arg1 = ( node * )a;
    const node *arg2 = ( node * ) b;
	if( arg1-> x < arg2-> x )
    return 1;
    else
    if( arg1-> x > arg2->x )
    return -1;
    else
    return 0;
}

int less_y(const void* a,const void* b){
    const node * arg1 = ( node * ) a;
    const node * arg2 = ( node * ) b;
    if( arg1-> y < arg2 ->y )
    return 1;
    else if ( arg1 -> y < arg2 -> y)
    return -1;
    else
	return 0;
}

void merge(int i,int mid,int j){
	int p=i,q=mid+1,r=i;
	while(p<=mid&&q<=j){                     
		if(nn[p].y<=nn[q].y+EPS)
		  tt[r++]=nn[p++];
		else
		  tt[r++]=nn[q++];
	}
	while(p<=mid)
	  tt[r++]=nn[p++];
	while(q<=j)
	  tt[r++]=nn[q++];
	for(r=i;r<=j;++r)
	  nn[r]=tt[r];
}
	
void mergesort(int i,int j){
	if(i==j) return;
	int mid=(i+j)/2;
	mergesort(i,mid);
	mergesort(mid+1,j);
	merge(i,mid,j);
} 

//void merge_x(int i,int mid,int j){
//	int p=i,q=mid+1,r=i;
//	while(p<=mid&&q<=j){
//		if(nn[p].x<=nn[q].x+EPS)
//		  tt[r++]=nn[p++];
//		else
//		  tt[r++]=nn[q++];
//	}
//	while(p<=mid)
//	  tt[r++]=nn[p++];
//	while(q<=j)
//	  tt[r++]=nn[q++];
//	for(r=i;r<=j;++r)
//	  nn[r]=tt[r];
//}
//	
//void mergesort_x(int i,int j){
//	if(i==j) return;
//	int mid=(i+j)/2;
//	mergesort_x(i,mid);
//	mergesort_x(mid+1,j);
//	merge_x(i,mid,j);
//} 

double rec_cal(int i,int j){
	double temp,delta;
	if(j-i<3){
//		//mergesort(i,j);
//		sort(nn+i,nn+j+1,less_y);
    qsort( nn + i , j - i , sizeof( node ) , less_y );
		delta=dist(nn[i],nn[i+1]);
		if(j-i==1)
		   return delta;
		temp=dist(nn[i+1],nn[i+2]);
		if(temp-delta<EPS)
		    delta=temp;
		temp=dist(nn[i],nn[i+2]);
		if(temp-delta<EPS)
		    delta=temp;
		return delta;
	}
	int k=(i+j)/2;
	double l=nn[k].x;
	double deltal=rec_cal(i,k);
	double deltar=rec_cal(k+1,j);
	delta=(deltal>deltar+EPS)?deltar:deltal;
//	merge(i,k,j);
//    sort(nn+i,nn+j+1,less_y);
qsort( nn + i , j - i , sizeof( node ) , less_y );
	int t=0,s;
	for(k=i;k<=j;++k)
	   if(nn[k].x+delta-l>EPS&&nn[k].x-l-delta<EPS)
	      v[t++]=nn[k];
	for(k=0;k<t;++k)
	   for(s=k+1;s<t&&s<=k+7;++s){
	       temp=dist(v[k],v[s]);
	       if(temp-delta<EPS)
	         delta=temp;
		}
	return delta;
}

int main(){
	int n,i;
	while(scanf("%d",&n),n!=0){
		for(i=0;i<n;++i)
		   scanf("%lf%lf",&nn[i].x,&nn[i].y);
//		mergesort_x(0,n-1);
qsort( nn , n - 1 , sizeof( int ) , less_x );
//	sort(nn,nn+n,less_x);
   qsort( nn , n - 1  , sizeof( node ) , less_x );
		printf("%.2lf\n",rec_cal(0,n-1)/2);
	}
	return 0;
}