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