P2632 Explorer

· · 题解

下文中 l_0, l_1 分别代指第一条，第二条直线。

直接两两连边，边数是 O((n + m)^2) 的，不可取。

考虑舍弃掉一些显然不优的的边：

  1. 对于一条直线，只用将相邻的点连边，边权为两者的距离。

  2. 对于两条直线上的点之间的边，假设 l_1 上的点为 (x_1, y_1)，向 l_0 做垂线，垂足横坐标为 x，找到 l_0 上横坐标离 x 最近的两个点，向其连边即可。

然后跑最小生成树。时间复杂度 O(n \log n)。

#include<cmath>
#include<cstdio>
#include<algorithm>
const int M=2e5+10,N=1e6+10;
const double inf = 1e20;

int n,m,ax,ay,bx,by,cx,cy,dx,dy;
double t0[M],t1[M];

struct Line{
    double k,b;
}l0,l1;

int fa[M];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[find(x)]=find(y);}
bool qry(int x,int y){return find(x)==find(y);}

double dist(double x1,double y1,double x2,double y2){
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

struct Edge{
    int u,v; double w;
}e[N];
int cnte;
double Kruskal(){
    for(int i=1;i<=n+m;i++) fa[i]=i;
    double sum=0;
    std::sort(e+1,e+1+cnte,[](Edge A,Edge B){return A.w<B.w;});
    for(int i=1;i<=cnte;i++){
        if(qry(e[i].u,e[i].v)) continue;
        merge(e[i].u,e[i].v),sum+=e[i].w;
    }
    return sum;
}

int main(){
    scanf("%d%d",&n,&m);
    scanf("%d%d%d%d",&ax,&ay,&bx,&by);
    scanf("%d%d%d%d",&cx,&cy,&dx,&dy);
    l0.k=(bx==ax)?inf:1.*(by-ay)/(bx-ax),l0.b=ay-ax*l0.k;
    l1.k=(dx==cx)?inf:1.*(dy-cy)/(dx-cx),l1.b=cy-cx*l1.k;

    double t;
    for(int i=1;i<=n;i++){
        scanf("%lf",&t);
        t0[i]=ax*t+bx*(1-t);
    }
    for(int i=1;i<=m;i++){
        scanf("%lf",&t);
        t1[i]=cx*t+dx*(1-t);
    }
    std::sort(t0+1,t0+1+n),std::sort(t1+1,t1+1+m);

    for(int i=1;i<=m;i++){
        double x1=t1[i],y1=l1.k*t1[i]+l1.b;
        double x=(y1+x1/l0.k-l0.b)/(l0.k+1./l0.k);
        int pos=std::lower_bound(t0+1,t0+1+n,x)-t0;
        for(int j=std::max(pos-1,1);j<=std::min(pos+1,n);j++)
            e[++cnte]=(Edge){i+n,j,dist(x1,y1,t0[j],l0.k*t0[j]+l0.b)};
    }
    for(int i=1;i<n;i++){
        double x0=t0[i],y0=l0.k*t0[i]+l0.b;
        double x1=t0[i+1],y1=l0.k*t0[i+1]+l0.b;
        e[++cnte]=(Edge){i,i+1,dist(x0,y0,x1,y1)};
    }
    for(int i=1;i<m;i++){
        double x0=t1[i],y0=l1.k*t1[i]+l1.b;
        double x1=t1[i+1],y1=l1.k*t1[i+1]+l1.b;
        e[++cnte]=(Edge){i+n,i+n+1,dist(x0,y0,x1,y1)};
    }
    printf("%.3f",Kruskal());
    return 0;
}

正确性的证明：

旋转平移坐标系使得 l_0 为 x 轴，显然答案不会变。

设旋转平移后 l_0 上点的横坐标为 x_{0,1},x_{0,2},\cdots,x_{0,n}，l_1 上的点横坐标为 x_{1,1},x_{1,2},\cdots,x_{1,m}。

对于 l_1 上的点 (x_{1,t},f(x_{1,t}))，如果要连向 l_0，显然找离 x_{1,t} 最接近的 x_{0,a},x_{0,a+1} 是最优的。

对于 l_0 上的点，如果没有任何一个 l_1 的点和他连边，那么它与 l_0 的旁边两个点连边显然是最优的。故并不需要 l_0 再向 l_1 做垂线找最近点。