题目链接:
题目大意:
给你两个人的位置和一个箱子的位置,然后给出n个瓶子的位置,要求让至少一个人去捡瓶子放到箱子里面去,一次只能拿一个瓶子,求把全部瓶子捡完之后的距离总和最小。解题思路:开始有两个起点A,B。除了从A或B出发拿瓶子并回到箱子距离不确定,其他时候肯定要从箱子到瓶子再回到箱子,距离就是dis(箱子到瓶子)*2.关于从A,B出发拿瓶子,分三种情况:①只有A拿②只有B拿③A拿一个瓶子,B拿一个瓶子(两个瓶子肯定不同)然后枚举即可。代码
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 double dis(int x,int y,int a,int b){ 8 return sqrt(1.0*(x-a)*(x-a)+1.0*(y-b)*(y-b)); 9 }10 11 int main(){12 int ax,ay,bx,by,tx,ty;13 scanf("%d%d%d%d%d%d",&ax,&ay,&bx,&by,&tx,&ty);14 double sum=0;15 double ma=1e18,mb=1e18,mab=1e18;16 int n;17 scanf("%d",&n);18 for(int i=1;i<=n;i++){19 int x,y;20 scanf("%d%d",&x,&y);21 double dt=dis(tx,ty,x,y);22 double da=dis(ax,ay,x,y)-dt;//让A拿的代价 23 double db=dis(bx,by,x,y)-dt;//让B拿的代价24 sum+=dt*2;25 mab=min(mab,min(ma+db,mb+da));26 ma=min(ma,da),mb=min(mb,db);27 }28 printf("%.12f",sum+min(mab,min(ma,mb)));//A拿一个B拿一个,或只让A拿,或只让B拿 29 return 0;30 }