Question

c++作业不会，求指导

某小区决定在小区内部建一家便利店，现小区内部共有八栋楼，它们的地理坐标分别为：（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）八栋楼的居民人数为权重，应该方便大多数人，实现总体最优。
其实我是搞不懂便利店应该建在8栋楼中，还是平面上任意一点，经过大家帮助我已经会前一种假设了，希望大家能告诉我如果是第二种假设，即如果便利店可以建在任意一点上应该怎么做，谢谢！

Answer 1

数据量很小又是明确的，完全可以用枚举法，就是一个一个来试。

下面我定义了一个结构体thr，有三个double型变量，x,y表示位置，如第一个是（10,20），z表示人数，第一个是30，  因为里面有小数，我为了简便干脆全部用double型。  然后按照数据初始化。

于是一个一个试，比如选第一个。在第一个里面的就不用动了（也就是 i 不等于 j 的原因），从第二个开始，算权重应该是所有人走的路程总和。  对于每个建筑物，就是与商店的距离乘以人数，距离是√((x1-x2)^2+(y1-y2)^2)，人数为z，也就是上式乘以z，  但是求开方还用库函数浪费时间，故直接把他们全部 平方 后再比较。((x1-x2)^2+(y1-y2)^2)*z^2。  就是平方后，数也比较小，完全可以用double。            ans[i]用来储存每个位置选为商店时权重和。  最后找最小的就行了

也可以不用ans[8]，直接找最小的，但是其他地方数据就没了，不方便查看。代码如下：

#include <iostream>
using namespace std;

struct thr
{
    double x;
    double y;
    double z;
};

thr test[8]={{10,20,30},{30,34,45},
{19,25,28},{38,49.1,8},{9,38.1,36},
{2,34,16},{5,8,78},{29,48,56}};

int main()
{
    double ans[8];
    for(int i=0;i<8;++i)
    {
        ans[i]=0;
        for(int j=0;j<8;++j)
        {
            if(i!=j)
            {
                ans[i]+=((test[i].x-test[j].x)
                *(test[i].x-test[j].x)+
                (test[i].y-test[j].y)*
                (test[i].y-test[j].y))*test[j].z
                *test[j].z;
            }
        }
    }
    double min=1000000000; int site;
    for(int i=0;i<8;++i)
    {
        cout<<ans[i]<<' ';
        if(ans[i]<min)
        {
            min=ans[i];
            site=i;
        }
    }
    cout<<endl;
    cout<<min<<" 位置是："<<site+1; 
    cout<<endl;
    system("pause");
}

计算出来，第3个位置最好，

追问

很感谢你的回答，我以为是在任意地点都可以建便利店，如果是这样的话该怎么做呢？

追答

那样的话貌似就更简单了，设点为（x，y），

比如对于第一个点，为 ((10-x)^2+(20-y)^2)*30^2 = 30^2 *((10^2-2*10*x+x^2)+(20^2-2*20*y+y^2)

就是展开二次方，8个加在一起，为两个分别关于x和y和一元二次方程，二次项系数大于0，一次项系数小于0，显然最小值在对称轴处取得，即-b/2*a；

关于这个一个一个加

就是累加 z^2，是x^2的系数，负的z^2*a*2是x的系数，就可以求对称轴了，

y的类似

下面只是求x的

double a=0,b=0;
    for(int i=0;i<8;++i)
    {
        a+=test[i].z*test[i].z;
        b+=test[i].z*test[i].z*test[i].x*2;
    }
    
    cout<<b/(2*a)<<endl;

结果与楼上略有不同，为15.168，，，不知道什么原因

Answer 2

坐标是(16.7,27)

代码如下

计算出每个点到所有居民的住处的距离综合，去最小值

#include <iostream>
#include <math.h>
using namespace std;


//居民楼类
class userModel
{
public:
	double x;//x坐标
	double y;//y坐标
	double usnum;//用户数
};
//便利店坐标
class pointModel
{
public:
	double x;
	double y;
};

double GetDistance(userModel *user,double i,double j)
{
	double distance=0;
	int n;
	for(n=0;n<8;n++)
	{
		distance+=sqrt((user[n].x-i)*(user[n].x-i)+(user[n].y-j)*(user[n].y-j))*(user[n].usnum);
	}
	return distance;
}



void main()
{
	userModel user[8]={
		{10,20,30},
		{30,34,45},
		{19,25,28},
		{38,49.1,8},
		{9,38.1,36},
		{2,34,16},
		{5,8,78},
		{29,48,56},
	};
	double i,j;
	pointModel point1;
	double distance1=100000,distance2;
	
	for(i=2.0;i<=38.0;i+=0.1)
	{
		for(j=8.0;j<=49.0;j++)
		{
			distance2=GetDistance(user,i,j);
			if(distance1>distance2)
			{
				distance1=distance2;
				point1.x=i;
				point1.y=j;
			}
		}
	}
	cout<<"point1.x="<<point1.x<<"\npoint1.y="<<point1.y<<"\ndistance1="<<distance1<<endl;
	system("pause");
	
}