Re: [問題] 求救!期中考第二三題(2000p)

看板Python作者gmccntzx1 (o.O)時間6年前 (2018/04/22 23:15)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串3/4 (看更多)

一點想法供你參考. 前提: 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