比赛 |
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;
}