https://codeforces.com/gym/102700/problem/A
开场看A，这不是我校2018校赛原题吗？然后一堆水题没写就开始写A，然后一直wa到2小时才过，罚时爆炸，水题大乱斗还是要先做水题才能使罚时和最小。。。
这题据别的队说直接求极值点然后算这样用Long double也过不了，必须要三分才能过，还好我运气好，一开始就用了三分。。。
基本的思路就是一起移动的地方三分，一个点停了以后就是一个点到线段最短距离
然后注意由于后面有用单位向量的地方，所以我们要保证除数不为0，需要特判起点终点重合的情况
然而这题距离是1e9级别的，而单位向量的长度又要精确到1e-6，所以double在三分里面会出现死循环，必须要用long double才行
#include<bits/stdc++.h> using namespace std; const double eps=1e-7; inline int sgn(double x) { if(x>-eps && x<eps) return 0; if(x<0) return -1; else return 1; } inline double mysqrt(double x) { return sqrt(max(0.0,x)); } struct point { double x,y; point(double a=0,double b=0) { x=a;y=b; } point operator + (const point &b)const { return point(x+b.x,y+b.y); } point operator - (const point &b)const { return point(x-b.x,y-b.y); } friend point operator * (const point &b,double t) { return point(b.x*t,b.y*t); } double norm() { return mysqrt(x*x+y*y); } }a,b,c,d; inline double det(const point &a,const point &b) { return a.x*b.y-a.y*b.x; } inline double dot(const point &a,const point &b) { return a.x*b.x+a.y*b.y; } inline double dist(point a,point b) { return (b-a).norm(); } inline double dis_point_seg(const point &p,const point &s,const point &t) { if(sgn(dot(p-s,t-s))<0) return (p-s).norm(); if(sgn(dot(p-t,s-t))<0) return (p-t).norm(); if(sgn(dist(s,t))==0) return dist(p,s); return fabs(det(s-p,t-p)/dist(s,t)); } int main() { scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y); scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y); double t1=(b-a).norm(),t2=(d-c).norm(),ans; long double l=0,r=min(t1,t2),mid,midd; if(sgn(r)==0) { if(sgn(t1)==0) ans=dis_point_seg(a,c,d); else ans=dis_point_seg(c,a,b); printf("%.8f",ans); return 0; } point da,dc,dda,ddc;double x; while(l+eps<r) { x=(r-l)/3; mid=l+x;midd=l+2*x; da=a+(b-a)*(mid/t1);dc=c+(d-c)*(mid/t2); dda=a+(b-a)*(midd/t1);ddc=c+(d-c)*(midd/t2); if(dist(da,dc)<dist(dda,ddc)) r=midd; else l=mid; } da=a+(b-a)*(l/t1);dc=c+(d-c)*(l/t2); ans=dist(da,dc); if(t1<t2) ans=min(ans,dis_point_seg(b,c+(d-c)*(t1/t2),d)); else ans=min(ans,dis_point_seg(d,a+(b-a)*(t2/t1),b)); printf("%.8f",ans); return 0; }
