记录编号	40498	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 信使问题b	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.580 s
提交时间	2012-07-17 20:14:01	内存使用	3.74 MiB

#include <cstdio>
#include <cstdlib>
#include <cmath>

#define I_F "postmanb.in"
#define O_F "postmanb.out"

const long MAXn=100000;
const double Pi=3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170680;
const double oo=1E32;

struct point
{
	long x,y;
	double r;
};
struct line
{
	double a, b, c;
};

long n;
point s[MAXn], ss[MAXn];
double maxl=0, minl=oo;
long tb[MAXn+2];
long tbl;

template<typename Any>
inline void Swap(Any&, Any&);
template<typename Any>
inline Any Max(const Any&, const Any&);
template<typename Any>
inline Any Min(const Any&, const Any&);
inline bool Comparea(const point&, const point&);
inline bool Compareb(const point&, const point&);
inline bool Comparec(const point&, const point&);
inline double Sqr(const double&);
inline double Abs(const double&);
inline double Len(const point&, const point&);
void Input();
void Sort(point*, const long&, const long&, bool (*Compare)(const point&, const point&));
void Prework();
inline double Cross(const point&, const point&, const point&);
void Gettb();
void Xzqk();
double Dfs(const point*, const point*, const long&);
void Output();

int main()
{
	Input();
	Prework();
	Sort(s,0,n-1,Compareb);
	Gettb();
	Xzqk();
	Sort(s,0,n-1,Comparec);
	Sort(ss,0,n-1,Comparea);
	minl=Min(minl,Dfs(s,ss,n));
	Output();
	return 0;
}

template<typename Any>
inline void Swap(Any &a, Any &b)
{
	Any t=a;
	a=b;
	b=t;
}

template<typename Any>
inline Any Max(const Any &a, const Any &b)
{
	return (a>b)?a:b;
}

template<typename Any>
inline Any Min(const Any &a, const Any &b)
{
	return (a<b)?a:b;
}

inline bool Comparea(const point &a, const point &b)
{
	return (a.y<b.y || (a.y==b.y && a.x<b.x));
}

inline bool Compareb(const point &a, const point &b)
{
	return (a.r<b.r);
}

inline bool Comparec(const point &a, const point &b)
{
	return (a.x<b.x || (a.x==b.x && a.y<b.y));
}

inline double Sqr(const double &x)
{
	return x*x;
}

inline double Len(const point &a, const point &b)
{
	return sqrt(Sqr(a.x-b.x)+Sqr(a.y-b.y));
}

inline double Abs(const double &x)
{
	return (x>0)?x:-x;
}

void Input()
{
	freopen(I_F,"r",stdin);
	scanf("%ld",&n);
	for (long i=0; i<n; ++i)
		scanf("%ld%ld",&s[i].x,&s[i].y);
}

void Sort(point *s, const long &l, const long &r, bool (*Compare)(const point&, const point&))
{
	if (r-l>20)
	{
		point x=s[l+rand()%(r-l+1)];
		long i=l, j=r;
		do
		{
			while (Compare(s[i],x)) ++i;
			while (Compare(x,s[j])) --j;
			if (i<=j)
				Swap(s[i++],s[j--]);
		} while (i<j);
		if (i<r) Sort(s,i,r,Compare);
		if (l<j) Sort(s,l,j,Compare);
	}
	else
	{
		bool flag=true;
		for (long i=l; i<r; ++i)
		{
			flag=false;
			for (long j=r; j>i; --j)
				if (Compare(s[j],s[j-1]))
					Swap(s[j],s[j-1]),
					flag=true;
		}
	}
}

void Prework()
{
	for (long i=1; i<n; ++i)
		if (Comparea(s[i],s[0]))
			Swap(s[i],s[0]);
	for (long i=1; i<n; ++i)
		s[i].r=atan2(s[i].y-s[0].y,s[i].x-s[0].x);
	for (long i=0; i<n; ++i)
		ss[i]=s[i];
}

inline double Cross(const point &a, const point &b, const point &c)
{
	return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
}

void Gettb()
{
	tb[0]=0;
	tb[1]=1;
	tbl=2;
	for (long i=2; i<n; ++i)
	{
		while (tbl>1 && Cross(s[tb[tbl-2]],s[tb[tbl-1]],s[i])>0)
			--tbl;
		tb[tbl++]=i;
	}
	while (tbl>1 && Cross(s[tb[tbl-2]],s[tb[tbl-1]],s[tb[0]])>0)
		--tbl;
}

void Xzqk()
{
	int q=1;
	tb[tbl++]=tb[0];
	for (int p=0; p<tbl-1; ++p)
	{
		while (Cross(s[tb[p]],s[tb[p+1]],s[tb[q]])>Cross(s[tb[p]],s[tb[p+1]],s[tb[q+1]]))
			q=(q+1)%tbl;
		maxl=Max(maxl,Max(Len(s[tb[p]],s[tb[q]]),Len(s[tb[p+1]],s[tb[q]])));
		while (Cross(s[tb[p]],s[tb[p+1]],s[tb[q]])==Cross(s[tb[p]],s[tb[p+1]],s[tb[q+1]]) && q!=p)
		{
			q=(q+1)%tbl;
			maxl=Max(maxl,Max(Len(s[tb[p]],s[tb[q]]),Len(s[tb[p+1]],s[tb[q]])));
		}
	}
}

double Dfs(const point *sx, const point *sy, const long &n)
{
	if (n==1)
		return oo;
	if (n==2)
		return Len(sx[0],sx[1]);
	long d=(n+1)/2;
	point v=sx[d];
	point *xl=new point[d], *xr=new point[n-d], *yl=new point[d], *yr=new point[n-d];
	for (long i=0; i<d; ++i)
		xl[i]=sx[i];
	for (long i=d; i<n; ++i)
		xr[i-d]=sx[i];
	long j=0, k=0;
	for (long i=0; i<n; ++i)
		if (Comparec(sy[i],v))
			yl[j++]=sy[i];
		else
			yr[k++]=sy[i];
	minl=Min(minl,Min(Dfs(xl,yl,d),Dfs(xr,yr,n-d)));
	
	j=0, k=0;
	point *syl=new point[d], *syr=new point[n-d];
	for (long i=0; i<d; ++i)
		if (v.x-yl[i].x<minl)
			syl[j++]=yl[i];
	for (long i=0; i<n-d; ++i)
		if (yr[i].x-v.x<minl)
			syr[k++]=yr[i];
	long t=0;
	for (long i=0; i<j; ++i)
	{
		while (syr[t].y<syl[i].y && t<k-1)
			++t;
		for (long l=Max((long)0,t-3); l<Min(k,t+4); ++l)
			minl=Min(minl,Len(syl[i],syr[l]));
	}
	return minl;
}

void Output()
{
	freopen(O_F,"w",stdout);
	printf("%lf\n%lf\n",maxl,minl);
}