2013数据结构课程设计之便利店选址(暴力枚举和随机函数两种做法)
[问题描述]
某小区决定在小区内部建一家便利店，现小区内部共有八栋楼，它们的地理坐标分别为：（10，20） （30，34） （19，25） （38，49.1） （9，38.1） （2，34） （5，8） （29，48）。同时，其中的住户人数分别为：30, 45, 28, 8, 36, 16, 78, 56。为了方便更多的住户购物，要求实现总体最优，请问便利店应该建立在哪里？
【提示】
1）便利店无论选址何处，八栋楼的居民均可直接到达，即八栋楼与便利店均相邻，且距离为直线距离；
2）八栋楼的居民人数为权重，应该方便大多数人，实现总体最优。
先是暴力找点的方法。
解题思路：自己开始想的就是暴力枚举，先找大范围，再找小范围。做这个题目就想到了的warmup2的1002题，但当时就是A不了。思路很简单，一步步地精确范围。先把整个地方划分成10*10的方格，再在里面找哪个最小，然后继续10*10每次都这样划分，精度确定跳出循环即可。详解见代码。
代码：
#include<iostream>#include<cstring>#include<string>#include<cmath>#include<cstdio>#include<algorithm>#include<ctime>using namespace std;int n; //n栋楼struct mq{ double x; double y; int peo;};mq node[1005];double cal(double px,double py) //计算值{ int i; double sum=0; for(i=0;i<n;i++) sum+=sqrt((px-node[i].x)*(px-node[i].x)+(py-node[i].y)*(py-node[i].y))*node[i].peo; return sum;}int main(){ int i; freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); double minx,miny,maxx,maxy,px,py; //找到四个边界 double ansx,ansy; //最后的结果 while(~scanf("%d",&n)) //n栋楼 { scanf("%lf%lf%d",&node[0].x,&node[0].y,&node[0].peo); minx=maxx=node[0].x; miny=maxy=node[0].y; //找到四个边界 for(i=1;i<n;i++) { scanf("%lf%lf%d",&node[i].x,&node[i].y,&node[i].peo); if(node[i].x<minx) minx=node[i].x; if(node[i].x>maxx) maxx=node[i].x; if(node[i].y<miny) miny=node[i].y; if(node[i].y>maxy) maxy=node[i].y; } minx*=100,maxx*=100,miny*=100,maxy*=100; //边界扩大一百倍 //找到边界了就可以随机了 int lenx,leny; lenx=ceil(maxx-minx),leny=ceil(maxy-miny); double sum=1000000000; srand((unsigned)time(NULL)); //播种 for(i=1;i<=500000;i++) //随机50W次 { px=rand()%lenx+minx; py=rand()%leny+miny; px/=100.0; py/=100.0; double tmp=cal(px,py); if(tmp<sum) { sum=tmp; ansx=px; ansy=py; } } cout<<"便利店选址坐标为:"<<endl; cout<<"x: "<<ansx<<" "<<"y: "<<ansy<<endl; cout<<"最优解为: "<<sum<<endl; } return 0;}/*810 20 3030 34 4519 25 2838 49.1 89 38.1 362 34 165 8 7829 48 56便利店选址坐标为:x: 16.56 y: 27.44最优解为: 5146.85*/