给你两条线及两条线上的点，求最小生成树。
可以挨个枚举一条线上的点，三分出另一条线上离他最近的点进行连边。
注意N、M可能为0
debug了1天半，至今不知道原始二分版本错在哪里。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 50010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
double x,y;
int id;
point(double x=,double y = ):x(x),y(y) {}
} p[N],q[N];
struct node
{
int u,v;
double w;
} ed[N<<];
int fa[N],g;
double t1[N],t2[N];
point a,b,c,d;
typedef point pointt;
point operator -(point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
} double dis(point a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
bool cmmp(node ta,node tb)
{
return ta.w<tb.w;
}
int findx(int x)
{
if(x!=fa[x])
fa[x] = findx(fa[x]);
return fa[x];
}
void add(point ta,point tb)
{
ed[++g].u = ta.id;
ed[g].v = tb.id;
ed[g].w = dis(ta-tb);
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int t,i,n,m;
int kk = ;
cin>>t;
while(t--)
{
scanf("%d%d",&n,&m);
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);
for(i = ; i <= n+m ; i++)
fa[i] = i;
for(i = ; i < n; i++)
{
scanf("%lf",&t1[i]); // cout<<p[i].x<<" "<<p[i].y<<endl;
}
for(i = ; i< m; i++)
{
scanf("%lf",&t2[i]); }
sort(t1,t1+n);
sort(t2,t2+m);
int h=;
for(i=;i<n;i++)
if(i==n-||t1[i]!=t1[i+])
t1[h++]=t1[i];
n=h;
h=;
for(i=;i<m;i++)
if(i==m-||t2[i]!=t2[i+])
t2[h++]=t2[i];
m=h;
for(i = ; i < n;i++)
{
p[i] = point(a.x*t1[i]+b.x*(-t1[i]),a.y*t1[i]+b.y*(-t1[i]));
p[i].id = i+;
}
for(i = ; i < m ; i++)
{
q[i] = point(c.x*t2[i]+d.x*(-t2[i]),c.y*t2[i]+d.y*(-t2[i]));
q[i].id = i+n+;
}
g = ;
double sum1 = ,sum2 = ;
for(i = ; i < n- ; i++)
{
add(p[i],p[i+]);
sum1+=dis(p[i]-p[i+]);
}
for(i = ; i < m- ; i++)
{
add(q[i],q[i+]);
sum2+=dis(q[i]-q[i+]);
}
if(n==||m==)
{ printf("Case #%d: %.3lf\n",++kk,sum1+sum2);
continue;
}
for(i = ; i < n; i++)
{
// point pp ;
// if(dcmp(c.x-d.x)==0)
// pp = point(c.x,p[i].y);
// else
// pp = dispoint(c,d,p[i]);
// if(dcmp(pp.x-min(c.x,d.x))<=0||dcmp(pp.x-max(c.x,d.x))>=0)
// {
// add(i,n+1);
// if(n+2<n+m)
// add(i,n+2);
// if(n+m-1>n+1)
// add(i,n+m-1);
// add(i,n+m);
// continue;
// }
// int k = find(n+1,n+m,c,dis(pp-c));
// cout<<p[k].id<<" "<<pp.x<<" "<<pp.y<<endl;
// add(i,k);
// if(k!=n+1)
// add(i,k-1);
// if(k!=n+m)
// add(i,k+1);
int l, r;
l = ;
r = m-;
while (r - l > )
{
int mid1 = (r + l) >> ;
int mid2 = (mid1 + r) >> ;
if (dis(p[i]-q[mid1]) > dis(p[i]-q[mid2]))
l = mid1;
else
r = mid2;
}
// int k = find(1,n,a,dis(pp-a));
add(p[i],q[l]);
add(p[i],q[r]);
if(l->=)
add(p[i],q[l-]);
if(r+<=m-)
add(p[i],q[r+]);
}
sort(ed+,ed+g+,cmmp);
int num = ;
double sum = ;
for(i = ; i <= g; i++)
{
int tx = findx(ed[i].u);
int ty = findx(ed[i].v);
if(tx!=ty)
{
fa[tx] = ty;
num++;
sum+=ed[i].w;
}
}
printf("Case #%d: %.3f\n",++kk,sum);
}
return ;
}