比赛 |
20110724 |
评测结果 |
C |
题目名称 |
遥远的距离 |
最终得分 |
0 |
用户昵称 |
Citron酱 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-24 12:12:43 |
显示代码纯文本
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#define I_F "faraway.in"
#define O_F "faraway.out"
#define MAXn (100000*2)
using namespace std;
struct Vec
{
long x,y;
};
ifstream fin(I_F);
ofstream fout(O_F);
long Input(Vec*,Vec&);
inline bool Same(Vec,Vec);
inline bool Compare(Vec,Vec,Vec);
inline void Swap(Vec&,Vec&);
void Qsort(Vec*,Vec,long,long);
inline bool Yz(Vec,Vec,Vec);
void Fuck2(Vec*,long,Vec*,Vec*,long,long);
inline double Sqr(long);
double Fuck(Vec*,long,Vec*,long);
int main()
{
short t;
long n,m1,m2;
Vec s[MAXn];
Vec g1[MAXn/2], g2[MAXn/2];
Vec l;
double ans;
fin>>t;
for (short i=0; i<t; i++)
{
n=Input(s,l);
Qsort(s,l,0,n-1);
Fuck2(s,n,g1,g2,m1,m2);
ans=Fuck(g1,m1,g2,m2);
fout<<setiosflags(ios::fixed)<<setprecision(3)<<ans<<endl;
}
fin.close();
fout.close();
return 0;
}
long Input(Vec s[MAXn], Vec &l)
{
int n,m;
fin>>n>>m;
n+=m;
for (long i=0; i<n; i++)
fin>>s[i].x>>s[i].y;
l=s[0];
for (long i=1; i<n; i++)
if ((s[i].x<l.x)||((s[i].x==l.x)&&(s[i].y<l.y)))
l=s[i];
}
inline bool Same(Vec a, Vec b)
{
return ((a.x==b.x)&&(a.y==b.y));
}
inline bool Compare(Vec l, Vec a, Vec b)
{
if (Same(a,l))
return true;
else if (Same(a,l))
return true;
else if ((a.x==l.x)&&(b.x==l.x))
if (a.y>b.y)
return true;
else
return false;
else if (b.x==l.x)
return true;
else if (a.x==l.x)
return false;
else
if ((a.y-l.y)/(a.x-l.x)<(b.y-l.y)/(b.x-l.x))
return true;
else
return false;
return false;
}
inline void Swap(Vec &a, Vec &b)
{
Vec t=a;
a=b;
b=t;
}
void Qsort(Vec s[MAXn], Vec y, long l, long r)
{
long x=l+rand()%(r-l+1);
long i=l, j=r;
do
{
while (Compare(y,s[i],s[x])) i++;
while (Compare(y,s[x],s[j])) j--;
if (i<=j)
Swap(s[i++],s[j--]);
} while (i>j);
if (i<r) Qsort(s,y,i,r);
if (l<j) Qsort(s,y,l,j);
}
inline bool Yz(Vec a, Vec b, Vec c)
{
return ((c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y)>0);
}
void Fuck2(Vec *s, long n, Vec *g1, Vec *g2, long &m1, long &m2)
{
Vec t[MAXn];
long tn=2;
t[0]=s[0];
t[1]=s[1];
for (long i=2; i<n; i++)
{
while (tn>1)
if (Yz(t[tn-2],t[tn-1],s[i]))
tn--;
else
{
t[tn++]=s[i];
break;
}
if (tn==1)
t[tn++]=s[i];
}
m1=0; m2=0;
for (long i=0; i<tn; i++)
if (t[i].x<0)
g1[m1++]=t[i];
else
g2[m2++]=t[i];
}
inline double Sqr(long x)
{
return x*x;
}
double Fuck(Vec g1[MAXn/2], long m1, Vec g2[MAXn/2], long m2)
{
double t=0,tt;
for (long i=0; i<m1; i++)
for (long j=0; j<m2; j++)
{
tt=sqrt(Sqr(g1[i].x-g2[j].x)+Sqr(g1[i].y-g2[j].y));
if (tt>t)
t=tt;
}
return t;
}