比赛 20120717 评测结果 AAAATTTTTT
题目名称 信使问题b 最终得分 40
用户昵称 QhelDIV 运行时间 3.221 s
代码语言 C++ 内存使用 13.74 MiB
提交时间 2012-07-17 11:55:53
显示代码纯文本
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("postmanb.in");
ofstream fout("postmanb.out");
int i,N,pos,n;
class Node
{
public:
	int x,y,pos;
}P[200000];
struct Point{

       double x,y;

};
class Vector
{
public:
	int x,y,pos;
}V[200000];
class S
{
public:
	int list[200000],top,pos;
	void push(int key)
	{
		list[++top]=key;
	}
	void pop()
	{
		top--;
	}
}Stack;
bool cmpx(Point *p1,Point *p2)

{

     return p1->x < p2->x;

}

bool cmpy(Point *p1,Point *p2)

{

     return p1->y < p2->y;

}

int CP(Vector a,Vector b)
{
	return a.x*b.y-a.y*b.x;
}

bool Cmp(Node a,Node b)
{
	if(CP(V[a.pos],V[b.pos])<0 || a.pos==pos)
		return true;
	return false;
}

void Initialize()
{
int i,Ymin=~0u>>1,Xmin=~0u>>1;
	fin>>N;
	for(i=1;i<=N;i++)
	{
		fin>>P[i].x>>P[i].y;
		if(P[i].y<Ymin || (P[i].y==Ymin && P[i].x<Xmin))
		{
			Ymin=P[i].x;
			Xmin=P[i].y;
			pos=i;
		}
	}
	for(i=1;i<=N;i++)
	{
		V[i].x=P[i].x-P[pos].x,V[i].y=P[i].y-P[pos].y;
		V[i].pos=i;P[i].pos=i;
	}
	sort(P+1,P+N+1,Cmp);
	for(i=1;i<=N;i++)
		P[i].pos=i;
}

void Graham_Scan()
{
Vector v,vv;
	Stack.push(P[1].pos);
	Stack.push(P[2].pos);
	for(i=3;i<=N;i++)
	{
		Stack.list[++Stack.top]=i;
		vv.x=P[Stack.list[Stack.top-1]].x-P[Stack.list[Stack.top-2]].x;
		vv.y=P[Stack.list[Stack.top-1]].y-P[Stack.list[Stack.top-2]].y;
		v.x=P[Stack.list[Stack.top]].x-P[Stack.list[Stack.top-1]].x;
		v.y=P[Stack.list[Stack.top]].y-P[Stack.list[Stack.top-1]].y;
		if(CP(v,vv)<0)
			Stack.list[--Stack.top]=i;
	}
//	for(i=1;i<=Stack.top;i++)
//		fout<<P[Stack.list[i]].x<<" "<<P[Stack.list[i]].y<<endl;
}

double Len(int a,int b)
{
	return sqrt(double(P[a].x-P[b].x)*(P[a].x-P[b].x)+(P[a].y-P[b].y)*(P[a].y-P[b].y));
}
Point point[200000],*px[200000],*py[200000];
inline double dis(Point *a,Point *b)
{
       return hypot((a->x-b->x),(a->y-b->y));
}


inline double min(double a,double b)

{

       return a < b ? a : b;

}

double closest(int l,int r)

{

       if(l+1 == r)

           return dis(px[l],px[r]);

       if(l+2 == r)

           return min(dis(px[l],px[l+1]),min(dis(px[l+1],px[r]),dis(px[l],px[r])));

       int mid = (l+r)/2;

       double ans = min(closest(l,mid),closest(mid+1,r));

       int i,cnt = 0,j;

       for(i = l; i <= r; i++)

           if(px[i]->x >= px[mid]->x-ans && px[i]->x <= px[mid]->x+ans)

               py[cnt++] = px[i];

       sort(py,py+cnt,cmpy);
       for(i = 0; i < cnt; i++)
         for(j = i+1; j < cnt; j++)
         {
               if(py[j]->y - py[i]->y >= ans)

                   break;

               ans = min(ans,dis(py[i],py[j]));

         }

       return ans;

}
void Solve()
{
	Graham_Scan();
int i,j;double Max=0,ans;
	for(i=1;i<=Stack.top;i++)
		for(j=i+1;j<=Stack.top;j++)
			Max=max(Max,Len(Stack.list[i],Stack.list[j]));
	fout<<setiosflags(ios::fixed)<<setprecision(6)<<Max<<endl;
	
	n=N;
        for(i = 0; i < n; i++)
        {
            point[i].x=P[i+1].x;point[i].y=P[i+1].y;
			px[i] = &point[i];
        }
        sort(px,px+n,cmpx);
        ans = closest(0,n-1);
	fout<<setiosflags(ios::fixed)<<setprecision(6)<<ans<<endl;
}

int main()
{
	Initialize();
	
	Solve();
	
	fin.close();
	fout.close();
	return 0;
}