zoj2107——Quoit Design

最近点对。不过，数据比较强，需对Y排序。

不断tle，直到重敲一遍代码才A！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxcost 1e100
#define maxn 100005
class point
{
public:
	double x,y;
};
point p[maxn];
bool cmp(point a,point b)
{
	if(a.x <b.x ) return true;
	return false;
}
int y[maxn];
bool cmpy(int a,int b)
{
	if(p[a].y<p[b].y) return true;
	return false;
}
double dist(point a,point b)
{
	return sqrt((a.x-b.x )*(a.x-b.x )+(a.y-b.y )*(a.y-b.y));
}
double min_dis(int left,int right)
{
	int i,j;
	double minlen=maxcost,resultl,resultr;
	if(right-left>2)
	{
		int mid=(left+right)>>1;
		resultl=min_dis(left,mid);
		resultr=min_dis(mid+1,right);
		minlen=resultl<resultr?resultl:resultr;
		int len=0;
		for(i=mid;i>=left&&p[i].x+minlen>p[mid].x ;i--)
			y[++len]=i;
		for(i=mid+1;i<=right&&p[mid].x +minlen>p[i].x ;i++)
			y[++len]=i;
		sort(y+1,y+len+1,cmpy);
		for(i=1;i<len;i++)
			for(j=i+1;j<=len;j++)
			{
				if(p[y[j]].y -p[y[i]].y>minlen) break;
				double dis=dist(p[y[j]],p[y[i]]);
				minlen=dis<minlen?dis:minlen;
			}
	}
	else 
	{
		double dis;
		for(i=left;i<right;i++)
			for(j=i+1;j<=right;j++)
			{
				dis=dist(p[i],p[j]);
				minlen=minlen<dis?minlen:dis;
			}
	}
	return minlen;
}
int main()
{
	int n,i;
	while(cin>>n&&n)
	{
		for(i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		sort(p,p+n,cmp);
		double result=min_dis(0,n-1);
		printf("%.2f\n",result/2);
	}
	return  0;
}