Submission #69878668

---

Source Code Expand

#include<bits/stdc++.h>
//bool Mst;
using namespace std;
namespace wyzfastio
{
	const char bool_str[2][6]={"false","true"};const int double_mx=12;
#define usefio
#ifdef usefio
	namespace __getchar{const int bufsize=1<<22;char buf[bufsize],*p1=buf,*p2=buf;inline char getchar(){return (p1==p2&&(p2=(p1=buf)+fread(buf,1,bufsize,stdin),p1==p2))?EOF:(*p1++);}}using __getchar::getchar;
	namespace __putchar{const int bufsize=1<<22;char buf[bufsize],*p=buf;inline void putchar(const char ch){if(p-buf==bufsize) fwrite(buf,1,bufsize,stdout),p=buf;*p++=ch;}inline void flush(){fwrite(buf,1,p-buf,stdout);}}using __putchar::putchar;using __putchar::flush;
	namespace __flusher{struct Flusher{Flusher(){}~Flusher(){flush();}}flusher;}
#endif
	struct istream{void tie([[maybe_unused]]int x){}};struct ostream{void tie([[maybe_unused]]int x){}};struct estream{};istream in;ostream out;
#ifdef LOCAL
	ostream err;
#else
	estream err;
#endif
	istream &operator>>(istream &in,char &s){s=getchar();while(s==' '||s=='\n'||s=='\r')s=getchar();return in;}
	istream &operator>>(istream &in,std::string &s){char ch=getchar();s.clear();while(ch==' '||ch=='\n'||ch=='\r')ch=getchar();while(!(ch==' '||ch=='\n'||ch=='\r'||ch==EOF))s+=ch,ch=getchar();return in;}
	istream &operator>>(istream &in,__int128 &x){char ch=getchar();int o=0;__int128 r=0;while(ch<'0'||ch>'9'){if(ch=='-')o^=1;ch=getchar();}while(ch>='0'&&ch<='9')r=(r<<3)+(r<<1)+ch-'0',ch=getchar();x=o?-r:r;return in;}
	istream &operator>>(istream &in,unsigned __int128 &x){char ch=getchar();__int128 r=0;while(ch>='0'&&ch<='9')r=(r<<3)+(r<<1)+ch-'0',ch=getchar();x=r;return in;}
	template<typename _Tp>inline typename std::enable_if<std::is_integral<_Tp>::value&&!std::is_same<_Tp,bool>::value,istream &>::type operator>>(istream &in,_Tp &x){char ch=getchar();int o=0;_Tp r=0;while(ch<'0'||ch>'9'){if(ch=='-')o^=1;ch=getchar();}while(ch>='0'&&ch<='9')r=(r<<3)+(r<<1)+ch-'0',ch=getchar();x=o?-r:r;return in;}
	template<typename _Tp>inline typename std::enable_if<std::is_same<_Tp,bool>::value,istream &>::type operator>>(istream &in,_Tp &x){int r;in>>r;x=r;}
	template<typename _Tp>inline typename std::enable_if<std::is_floating_point<_Tp>::value,istream &>::type operator>>(istream &in,_Tp &x){_Tp r=0,p=1;int op=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')op=-op;ch=getchar();}while(ch>='0'&&ch<='9'){r=r*10+ch-'0';ch=getchar();}if(ch=='.'){ch=getchar();while(ch>='0'&&ch<='9')r+=(p*=0.1)*(ch-'0'),ch=getchar();}x=r*op;return in;}
	ostream &operator<<(ostream &out,const char x){putchar(x);return out;}
	ostream &operator<<(ostream &out,const char *s){while(*s!='\0'&&*s!=EOF)putchar(*s),s++;return out;}
	ostream &operator<<(ostream &out,std::string s){for(char ch:s)putchar(ch);return out;}
	ostream &operator<<(ostream &out,__int128 x){static int __stk[66];int top=0,op=1-((x<0)<<1);if(x==0)__stk[top++]=0;else while(x)__stk[top++]=(x%10)*op,x/=10;if(op==-1)putchar('-');while(top)putchar(__stk[--top]+'0');return out;}
	ostream &operator<<(ostream &out,unsigned __int128 x){static int __stk[66];int top=0;if(x==0)__stk[top++]=0;else while(x)__stk[top++]=(x%10),x/=10;while(top)putchar(__stk[--top]+'0');return out;}
	template<typename _Tp>inline typename std::enable_if<std::is_integral<_Tp>::value&&!std::is_same<_Tp,bool>::value,ostream &>::type operator<<(ostream &out,_Tp x){static int __stk[33];int top=0,op=1-((x<0)<<1);if(x==0)__stk[top++]=0;else while(x)__stk[top++]=(x%10)*op,x/=10;if(op==-1)putchar('-');while(top)putchar(__stk[--top]+'0');return out;}
	template<typename _Tp>inline typename std::enable_if<std::is_same<_Tp,bool>::value,ostream &>::type operator<<(ostream &out,_Tp x){out<<bool_str[x];return out;}
	template<typename _Tp>inline typename std::enable_if<std::is_floating_point<_Tp>::value,ostream &>::type operator<<(ostream &out,_Tp x){if(x<0)putchar('-'),x=-x;static int __stk[233];int top=0;for(int i=0;i<double_mx;i++)x*=10;x=std::floor(x+0.5);for(_Tp y;x>=1;)y=std::floor(x/10),__stk[top++]=x-y*10,x=y;while(top<=double_mx)__stk[top++]=0;while(top>double_mx)putchar(__stk[--top]+'0');putchar('.');while(top)putchar(__stk[--top]+'0');return out;}
	template<typename _Tp>inline estream &operator<<(estream &err,[[maybe_unused]]_Tp x){return err;}
#define cin wyzfastio::in
#define cout wyzfastio::out
#define cerr wyzfastio::err
}
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
struct point
{
	ld x,y;
	point(ld _x=0,ld _y=0):x(_x),y(_y){}
};
struct vec
{
	ld x,y;
	vec(ld _x=0,ld _y=0):x(_x),y(_y){};
	vec(point st,point en):x(en.x-st.x),y(en.y-st.y){}
};
ld alpha(vec x){return atan2l(x.y,x.x);}
ld sq(ld x){return x*x;}
ld len(vec x){return sqrtl(sq(x.x)+sq(x.y));}
ld len2(vec x){return sq(x.x)+sq(x.y);}
ld operator*(vec x,vec y){return x.x*y.y-x.y*y.x;}
struct line
{
	point a,b;
	line(point _a=point(0,0),point _b=point(0,0)):a(_a),b(_b){}
	ld len(){return ::len(vec(a,b));}
	ld len2(){return ::len2(vec(a,b));}
};
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{
		line l1,l2;
		cin>>l1.a.x>>l1.a.y>>l1.b.x>>l1.b.y;
		ld dx1=(l1.b.x-l1.a.x)/l1.len();
		ld dy1=(l1.b.y-l1.a.y)/l1.len();
		cin>>l2.a.x>>l2.a.y>>l2.b.x>>l2.b.y;
		ld dx2=(l2.b.x-l2.a.x)/l2.len();
		ld dy2=(l2.b.y-l2.a.y)/l2.len();
		if(l1.len2()>l2.len2()) swap(l1,l2);
		ld T=sqrtl(l1.len2());
		ld T2=sqrtl(l2.len2());
		auto f=[&](ld t)->ld
		{
			return line(point(l1.a.x+dx1*t,l1.a.y+dy1*t),point(l2.a.x+dx2*t,l2.a.y+dy2*t)).len();
		};
		auto f2=[&](ld t)->ld
		{
			return line(l1.b,point(l2.a.x+dx2*t,l2.a.y+dy2*t)).len();
		};
		ld le=0,ri=T;
		while(ri-le>=1e-8)
		{
			ld lmid=le+(ri-le)/3,rmid=ri-(ri-le)/3;
			if(f(lmid)>f(rmid)) le=lmid;
			else ri=rmid;
		}
		ld ans=f(le);
		le=T,ri=T2;
		while(ri-le>=1e-8)
		{
			ld lmid=le+(ri-le)/3,rmid=ri-(ri-le)/3;
			if(f2(lmid)>f2(rmid)) le=lmid;
			else ri=rmid;
		}
		ans=min(ans,f2(le));
		cout<<ans<<"\n";
	}
	return 0;
}

Submission Info

Judge Result