How Long Do You Have to Draw

1
0 1
2 3
1 3
0 2 4

Case #1: 5.66

题意：两条平行线。各有n、m个点。要连一些线，两个端点各自是两条平行线上的点。而且不能交叉。

在取得最多三角形的情况下，求最小的总的线的长度。

题解：要保证有最多的三角形 得把全部的点都连上。这样先把两平行线的最左端两点先连上，再依次把两条平行线最左端没连的选距离小的连上。

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 100010

using namespace std;

double a[N],b[N];

int main() {
    //freopen("test.in","r",stdin);
    int t;
    cin>>t;
    int ca=1;
    while(t--) {
        double y1,y2;
        scanf("%lf%lf",&y1,&y2);
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++) {
            scanf("%lf",&a[i]);
        }
        for(int j=0; j<m; j++) {
            scanf("%lf",&b[j]);
        }
        sort(a,a+n);
        sort(b,b+m);
        printf("Case #%d: ",ca++);
        if(n==1&&m==1) {
            printf("0.00\n");
            continue;
        }
        if(n==0||m==0) {
            printf("0.00\n");
            continue;
        }
        double ans=sqrt((y1-y2)*(y1-y2)+(a[0]-b[0])*(a[0]-b[0]));
        int l1=1,l2=1;
        while(l1<n&&l2<m) {
            double dis1=(y1-y2)*(y1-y2)+(a[l1]-b[l2-1])*(a[l1]-b[l2-1]);
            double dis2=(y1-y2)*(y1-y2)+(a[l1-1]-b[l2])*(a[l1-1]-b[l2]);
            if(dis1<dis2) {
                ans+=sqrt(dis1);
                l1++;
            } else {
                ans+=sqrt(dis2);
                l2++;
            }
        }
        while(l1<n) {
            double dis1=(y1-y2)*(y1-y2)+(a[l1]-b[l2-1])*(a[l1]-b[l2-1]);
            ans+=sqrt(dis1);
            l1++;
        }
        while(l2<m) {
            double dis2=(y1-y2)*(y1-y2)+(a[l1-1]-b[l2])*(a[l1-1]-b[l2]);
            ans+=sqrt(dis2);
            l2++;
        }
        printf("%.2f\n",ans );
    }
    return 0;
}