比赛 20110724 评测结果 AAAATTWTTT
题目名称 遥远的距离 最终得分 40
用户昵称 PurpleShadow 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-24 11:33:48
显示代码纯文本
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
struct point
{
	int X,Y;
	point(){}
	point(const int &_X,const int &_Y):
	X(_X),Y(_Y){}
	bool operator<(const point &t)const
	{return X<t.X||X==t.X&&Y<t.Y;}
	point operator-(const point &t)
	{return point(X-t.X,Y-t.Y);}
	bool cross(const point& t)
	{return (long long)X*t.Y-(long long)Y*t.X<=0;}
};
int n[2],top[2];
point S[2][N];
void getHull(int& n,point* S,int& top)
{
	static bool flag[N];
	static point P[N];
	static int s[N];
	int i,k;
	for (i=1;i<=n;++i)
		scanf("%d%d",&P[i].X,&P[i].Y);
	sort(P+1,P+n+1);
	memset(flag,0,sizeof(flag));
	for (i=1;i<=n;++i)
	{
		while (top>1&&(P[i]-P[s[top]]).cross(P[s[top]]-P[s[top-1]])) flag[s[top--]]=0;
		s[++top]=i;
		flag[i]=1;
	}
	k=top;flag[1]=0;
	for (i=n;i>0;--i)
	if (!flag[i])
	{
		while (top>k&&(P[i]-P[s[top]]).cross(P[s[top]]-P[s[top-1]])) --top;
		s[++top]=i;
	}
	for (i=1;i<top;++i) S[i]=P[s[i]];
	--top;
}
void init()
{
	scanf("%d%d",n,n+1);
}
inline double dis(const point& a,const point &b)
{
	double t1=a.X-b.X,t2=a.Y-b.Y;
	return sqrt(t1*t1+t2*t2);
}
double getAns(point* a,point* b,int n,int m)
{
	int i,j;
	double ans=0;
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			ans=max(ans,dis(a[i],b[j]));
	return ans;
}
void slove()
{
	getHull(n[0],S[0],top[0]);
	getHull(n[1],S[1],top[1]);
	printf("%.3lf\n",getAns(S[0],S[1],top[0],top[1]));
}
int main()
{
freopen("faraway.in","r",stdin);
freopen("faraway.out","w",stdout);
	int t;
	scanf("%d",&t);
	while (t--)
	{
		init();
		slove();
	}
	return 0;
}