【题意】有两个人A,B在一个二维平面上捡瓶子放到垃圾箱里,每个人从从初始位置出发,一次只能选择一个瓶子去捡,然后去垃圾箱,再去捡瓶子。。。也可以中途不捡了,给出A,B,垃圾箱和n个瓶子的坐标,求两个人捡完瓶子要的最短距离。
【分析】把距离都求出来,再贪心找到最小距离就好了
【Trick】见代码吧。
【AC代码】
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100003;
struct node{
int id;
double val;
node(){}
node(int id,double val):id(id),val(val){}
bool operator<(const node &rhs)const{
return val<rhs.val;
}
}a[maxn],b[maxn];
double x[maxn],y[maxn];
double get_dis(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double ax,ay,bx,by,tx,ty;
int n;
int main(){
scanf("%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&tx,&ty);
scanf("%d",&n);
for(int i=1; i<=n; i++) cin>>x[i]>>y[i];
for(int i=1; i<=n; i++){
a[i].id=i;
a[i].val = get_dis(x[i],y[i],ax,ay)-get_dis(x[i],y[i],tx,ty);
}
sort(a+1,a+n+1);
//Init
for(int i=1; i<=n; i++){
b[i].id=i;
b[i].val = get_dis(x[i],y[i],bx,by)-get_dis(x[i],y[i],tx,ty);
}
sort(b+1,b+n+1);
double ans = 0;
for(int i=1; i<=n; i++) ans+=2.00*get_dis(x[i],y[i],tx,ty);
// cout<<ans<<endl;
double temp = ans;
a[0]=node{0,0};
b[0]=node{0,0};
ans = min(ans+a[1].val,ans+b[1].val);
//本题的Trick点
//必须要有一个人动,才能捡完垃圾
//之前循环里面,有可能ans就是最小的,就一直更新不了,这样就代表没人动,是不行的
for(int ii=0; ii<3; ii++){//A动B不动
for(int jj=0; jj<3; jj++){
if(ii==0&&jj==0)continue;
if(a[ii].id==b[jj].id) continue;
ans = min(ans,temp+a[ii].val+b[jj].val);
}
}
printf("%.8f\n",ans);
return 0;
}