比赛 20110724 评测结果 AAAAAAAAAA
题目名称 遥远的距离 最终得分 100
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-24 12:24:06
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

#define pb push_back
const int MAXN=100005;

struct Point
{
	int x,y;
	Point (int _x=0,int _y=0):x(_x),y(_y){}
	Point operator - (const Point &b) const
	{
		return Point (x-b.x,y-b.y);
	}
	long long operator * (const Point &b) const
	{
		return (long long )x*b.y-(long long)y*b.x;
	}
}A[MAXN],B[MAXN];

bool operator < (const Point &a,const Point &b)
{
	return a.y<b.y || (a.y==b.y && a.x<b.x);
}

long long sqr(long long x)
{
	return x*x;
}

inline double getdis(const Point &a,const Point &b)
{
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}

inline double abs(const Point &x)
{
	return sqrt(sqr(x.x)+sqr(x.y));
}

inline double getdis(const Point &a,const Point &b,const Point &c)
{
	return fabs((b-a)*(c-a)/double(abs(a-b)));
}

inline void Max(double &a,double b)
{
	if (b>a)
		a=b;
}

bool cmp1(long long x)
{
	return x<=0;
}

bool cmp2(long long x)
{
	return x>=0;
}

void gethull(vector<Point> &v,Point *P,int N)
{
	sort(P,P+N);
	v.pb(P[0]);
	v.pb(P[1]);
	int size;
	for(int i=2;i<N;i++)
	{
		while((size=v.size())>=2 && cmp1((v[size-1]-v[size-2])*(P[i]-v[size-1])))
			v.pop_back();
		v.push_back(P[i]);
	}
	int tmp=v.size();
	v.pb(P[N-2]);
	for(int i=N-3;i>=0;i--)
	{
		while((size=v.size())>tmp && cmp1((v[size-1]-v[size-2])*(P[i]-v[size-1])))
			v.pop_back();
		v.push_back(P[i]);
	}
	v.pop_back();
}

void split(const vector<Point> &v,vector<Point> &v1,vector<Point> &v2)
{
	int k=-1;
	int N=v.size();
	for(int i=0;i<N;i++)
		if (v[i].x>0 && v[(i-1+N)%N].x<0)
		{
			k=i;
			break;
		}
	for(int j=k;;j=(j+1)%N)
	{
		if (v[j].x<0)
		{
			k=j;
			break;
		}
		v2.push_back(v[j]);
	}
	for(int j=k;;j=(j+1)%N)
	{
		if (v[j].x>0)
			break;
		v1.push_back(v[j]);
	}
	reverse(v1.begin(),v1.end());
}

int main()
{
	freopen("faraway.in","r",stdin);
	freopen("faraway.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int N,M;
		scanf("%d%d",&N,&M);
		for(int i=0;i<N;i++)
			scanf("%d%d",&A[i].x,&A[i].y);
		for(int i=N;i<N+M;i++)
			scanf("%d%d",&A[i].x,&A[i].y);
		vector<Point> v,v1,v2;
		gethull(v,A,N+M);
		split(v,v1,v2);
		int size1=v1.size(),size2=v2.size();
		int j=size2-1;
		double re=0;
		for(int i=0;i+1<size1;i++)
		{
			while(j>0 && getdis(v1[i],v1[i+1],v2[j])<=getdis(v1[i],v1[i+1],v2[j-1]))
				j--;
			Max(re,getdis(v1[i],v2[j]));
			Max(re,getdis(v1[i+1],v2[j]));
		}
		swap(v1,v2);
		size1=v1.size(),size2=v2.size();
		j=size2-1;
		for(int i=0;i+1<size1;i++)
		{
			while(j>0 && getdis(v1[i],v1[i+1],v2[j])<=getdis(v1[i],v1[i+1],v2[j-1]))
				j--;
			Max(re,getdis(v1[i],v2[j]));
			Max(re,getdis(v1[i+1],v2[j]));
		}
		printf("%.3lf\n",re);
	}
	return 0;
}