求助!我的代码:
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll int
using namespace std;
struct ed{
ll u,v;
double d;
};
bool cmp(ed a,ed b){
return a.d<b.d;
}
ll n,m;
double a1[200005],a2[200005];
double dis(double ax,double ay,double bx,double by){
return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}
ll f[200005];
ll find(ll x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
ed e[600000];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n+m;++i) f[i]=i;
double ax,ay,bx,by;
double cx,cy,dx,dy;
scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);
double k1=/*((by-ay==0)||(bx-ax)==0)?0:*/(by-ay)/(bx-ax);
double b1=ay-k1*ax;
double k2=/*(((dy-cy)==0)||(dx-cx==0))?0:*/(dy-cy)/(dx-cx);
double b2=cy-k2*cx;
double t;
for(int i=1;i<=n;++i){
scanf("%lf",&t);
a1[i]=ax*t+bx*(1-t);
}
for(int i=1;i<=m;++i){
scanf("%lf",&t);
a2[i]=cx*t+dx*(1-t);
}
sort(a1+1,a1+1+n);
sort(a2+1,a2+m+1);
ll tot=0;
for(int i=1;i<=m;++i){
double x=a2[i];
double y=x*k2+b2;
double k=-k1;
double b=y-k*x;
double nx=/*((b-b1)==0||(k1-k)==0)?0:*/(b-b1)/(k1-k);
ll o=lower_bound(a1+1,a1+1+n,nx)-a1;
if(o<1||o>n) continue;
for(int j=max((ll)1,o-1);j<=max(n,o+1);++j){
// e[++tot]=(ed){i+n,j,dis(x,y,a1[j],a1[j]*k1+b1)};//
e[++tot]=(ed){1,2,212};
}
}
for(int i=1;i<n;++i){
e[++tot]=(ed){i,i+1,dis(a1[i],a1[i]*k1+b1,a1[i+1],a1[i+1]*k1+b1)};
}
for(int i=1;i<m;++i){
e[++tot]=(ed){i+n,i+1+n,dis(a2[i],a2[i]*k1+b1,a2[i+1],a2[i+1]*k1+b1)};
}
//5m+n=6e5
sort(e+1,e+1+tot,cmp);
double sum=0;
ll cnt=0;
for(int i=1;i<=tot;++i){
ll fu=find(e[i].u);
ll fv=find(e[i].v);
if(fu!=fv){
f[fu]=fv;
sum+=e[i].d;
cnt++;
if(cnt==n+m-1){
break;
}
}
}
printf("%.3lf\n",sum);
return 0;
}