比赛 20110724 评测结果 WAATTTWTTT
题目名称 遥远的距离 最终得分 20
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-24 10:43:31
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=100111;

struct point
{
	double x,y;
}A[MAXN],B[MAXN],ta[MAXN],tb[MAXN],z;

int DAT,n,i,j,k,m;
double x,y,ans;

inline double dis(point A,point B)
{
	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

inline int cmp(const void *p,const void *q)
{
	point *A,*B;
	A=(point *)p;
	B=(point *)q;
	return abs(A->x)+abs(A->y)-abs(B->x)-abs(B->y);
}

int main()
{
	freopen("faraway.in","r",stdin);
	freopen("faraway.out","w",stdout);
	scanf("%d",&DAT);
	while (DAT--)
	{
		scanf("%d%d",&n,&m);
		for (i=1;i<=n;i++)
			scanf("%lf%lf",&A[i].x,&A[i].y);
		for (i=1;i<=m;i++)
			scanf("%lf%lf",&B[i].x,&B[i].y);
		qsort(A+1,n,sizeof(point),cmp);
		qsort(B+1,n,sizeof(point),cmp);
		ans=0;
		long long N,M;
		N=n;
		M=m;
		if (N*M<=10000000)
		{
			for (i=1;i<=n;i++)
				for (j=1;j<=m;j++)
					ans=max(ans,dis(A[i],B[j]));
		}
		else
		{
			if (N>10000 && M>10000)
				for (i=1;i<=10000;i++)
					for (j=1;j<=10000;j++)
						ans=max(ans,dis(A[i],B[j]));
			else
				if (N<M)
				{
					for (i=1;i<=N;i++)
						for (j=1;j<=10000000/N;j++)
							ans=max(ans,dis(A[i],B[j]));
				}
				else
					for (i=1;i<=10000000/M;i++)
						for (j=1;j<=M;j++)
							ans=max(ans,dis(A[i],B[j]));;
		}			
		printf("%0.3lf\n",ans);
	}
	return 0;
}