一点想法供你参考.
前提:
1. 卖场不一定会设在里中心
2. 构成的正方形领域不是特定的转向
3. 人口集中在里中心
步骤:
1. 从资料中找所有两点距离≦3*(2^0.5) km的组合 (即先找出以两点作
为正方形对角顶点的组合)
2. 在步骤1的结果中,从两点距离最接近3*(2^0.5) km的组合开始依序往
距离越来越小的组合执行以下步骤:
a. 一一判断其他点是否在此两点构成的正方形范围内?
是的话,记录下来.
b. 将所有在此正方形范围内的里的人口数加总起来
3. 找到步骤2b中人口数加总后最多的组合. 而卖场的座标就在该组合正
方形对角两点的中点.
备注:
1. 在步骤2a中,要确认点是否在正方形内,可以参考下图,检查d是否≦l.
但要先确认theta是否为锐角,否则要用A,O,P点来算.
https://imgur.com/k4hLfqm
2. 步骤2是由大至小开始寻找的,也是为了确保不会有以下的情况发生:
因为找到的组合是距离≦3*(2^0.5) km,表示即使是距离最大的组合
,该正方形的对角线也可能不足3*(2^0.5) km.
假设有一点P可以因为正方形稍微扩大而被围进,表示实际上尚有对角
线更接近3*(2^0.5) km的组合.
但是因为步骤2已经是由最接近3*(2^0.5) km的组合开始寻找,因此可
以反证上述假设不会成立.
https://imgur.com/3mbyv9n