比赛 20120717 评测结果 AAWWWWWW
题目名称 信使问题b 最终得分 30
用户昵称 了反取字名我擦 运行时间 0.785 s
代码语言 C++ 内存使用 5.81 MiB
提交时间 2012-07-17 11:37:13
显示代码纯文本
#include<fstream>
#include<algorithm>
#include<string>
#include<cmath>

using namespace std;
ifstream fi("postmanb.in");
ofstream fo("postmanb.out");

int n;
double M=0,m=99999999;
struct point
{
	int x;
	int y;
}p[100001],res[100001];
int cmp(point p1,point p2)
{
	return p1.y<p2.y||(p1.y==p2.y&&p1.x<p2.x);
}
bool ra(point p1,point p2,point p3)
{
	return (p2.x-p1.x)*(p3.y-p1.y)>(p3.x-p1.x)*(p2.y-p1.y);
}
int main()
{
	fi>>n;
	for(int i=0;i<n;i++)
		fi>>p[i].x>>p[i].y;
	sort(p,p+n,cmp);
	res[0]=p[0];
	res[1]=p[1];
	int top=1;
	for(int i=2;i<n;i++)
	{
		while(top&&!ra(res[top],res[top-1],p[i]))
			top--;
		res[++top]=p[i];
	}
	int len=top;
	res[++top]=p[n-2];
	for(int i=n-3;i>=0;i--)
	{
		while(top!=len&&!ra(res[top],res[top-1],p[i]))
			top--;
		res[++top]=p[i];
	}
	for(int i=0;i<top;i++)
		for(int j=i+1;j<top;j++)
			if(sqrt((double)((res[i].x-res[j].x)*(res[i].x-res[j].x)+(res[i].y-res[j].y)*(res[i].y-res[j].y)))>M)
				M=sqrt((double)((res[i].x-res[j].x)*(res[i].x-res[j].x)+(res[i].y-res[j].y)*(res[i].y-res[j].y)));
	fo<<M<<endl;
	if(n<=10000)
	{
		for(int i=0;i<n;i++)
			for(int j=i+1;j<n;j++)
				if(sqrt((double)((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)))<m)
					m=sqrt((double)((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)));
		fo<<m;
	}
	fi.close();
	fo.close();
	return 0;
}