直接无脑求交点然后求最短路了
#include<bits/stdc++.h> using namespace std; typedef double db; const db eps=1e-8; const db pi=acos(-1); int sign(db k){ if (k>eps) return 1; else if (k<-eps) return -1; return 0; } int cmp(db k1,db k2){return sign(k1-k2);} int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}// k3 在 [k1,k2] 内 struct point{ db x,y; point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};} point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};} point operator * (db k1) const{return (point){x*k1,y*k1};} point operator / (db k1) const{return (point){x/k1,y/k1};} db abs(){return sqrt(x*x+y*y);} db abs2(){return x*x+y*y;} db dis(point k1){return ((*this)-k1).abs();} point unit(){db w=abs(); return (point){x/w,y/w};} }; db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;} int intersect(db l1,db r1,db l2,db r2){ if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2); return cmp(r1,l2)!=-1&&cmp(r2,l1)!=-1; } int checkSL(point k1,point k2,point k3,point k4){//线段和直线严格相交 int sign1 = sign(cross(k3-k1,k4-k1)); int sign2 = sign(cross(k3-k2,k4-k2)); return sign(cross(k3-k1,k4-k1))*sign(cross(k3-k2,k4-k2))<0; } point getSL(point k1,point k2,point k3,point k4){ db w1=cross(k1-k3,k4-k3),w2=cross(k4-k3,k2-k3); return (k1*w2+k2*w1)/(w1+w2); } point p[10],k1,k2; db a,b,c,x1,y1,x2,y2,dis[10][10],d[10]; int tot,v[10]; void dij(){ for(int i=1;i<=6;i++)d[i]=1e16,v[i]=0; d[1]=0; for(int i=1;i<=6;i++){ int now;db Min=1e16; for(int j=1;j<=6;j++) if(Min>d[j] && v[j]==0){ Min=d[i];now=j; } v[now]=1; for(int j=1;j<=6;j++) if(!v[j])d[j]=min(d[j],d[now]+dis[now][j]); } } //ax+by+c=0 int main(){ cin>>a>>b>>c>>x1>>y1>>x2>>y2; p[1]=(point){x1,y1};p[2]=(point){x1,y2}; p[3]=(point){x2,y2};p[4]=(point){x2,y1}; if(a==0){ k1=(point){0,-c/b}; k2=(point){1,-c/b}; }else if(b==0){ k1=(point){-c/a,0}; k2=(point){-c/a,1}; }else { k1=(point){0,-c/b}; k2=(point){1,(-c-a)/b}; } for(int i=1;i<=6;i++) for(int j=1;j<=6;j++) dis[i][j]=1e16; tot=4; if(sign(a*p[1].x+b*p[1].y+c)==0){ p[++tot]=p[1]; dis[1][tot]=dis[tot][1]=0; } if(sign(a*p[2].x+b*p[2].y+c)==0){ p[++tot]=p[2]; dis[2][tot]=dis[tot][2]=0; } if(sign(a*p[3].x+b*p[3].y+c)==0){ p[++tot]=p[3]; dis[3][tot]=dis[tot][3]=0; } if(sign(a*p[4].x+b*p[4].y+c)==0){ p[++tot]=p[4]; dis[4][tot]=dis[tot][4]=0; } if(checkSL(p[1],p[2],k1,k2)){ point k3=getSL(p[1],p[2],k1,k2); p[++tot]=k3; dis[1][tot]=dis[tot][1]=k3.dis(p[1]); dis[2][tot]=dis[tot][2]=k3.dis(p[2]); } if(checkSL(p[2],p[3],k1,k2)){ point k3=getSL(p[2],p[3],k1,k2); p[++tot]=k3; dis[3][tot]=dis[tot][3]=k3.dis(p[3]); dis[2][tot]=dis[tot][2]=k3.dis(p[2]); } if(checkSL(p[3],p[4],k1,k2)){ point k3=getSL(p[3],p[4],k1,k2); p[++tot]=k3; dis[3][tot]=dis[tot][3]=k3.dis(p[3]); dis[4][tot]=dis[tot][4]=k3.dis(p[4]); } if(checkSL(p[4],p[1],k1,k2)){ point k3=getSL(p[4],p[1],k1,k2); p[++tot]=k3; dis[1][tot]=dis[tot][1]=k3.dis(p[1]); dis[4][tot]=dis[tot][4]=k3.dis(p[4]); } dis[1][2]=dis[2][1]=p[1].dis(p[2]); dis[2][3]=dis[3][2]=p[2].dis(p[3]); dis[3][4]=dis[4][3]=p[3].dis(p[4]); dis[4][1]=dis[1][4]=p[1].dis(p[4]); dis[5][6]=dis[6][5]=p[5].dis(p[6]); if(tot==4){ printf("%.10lf ",fabs(x1-x2)+fabs(y1-y2)); } else { dij(); printf("%.10lf ",d[3]); } }