題目:https://leetcode-cn.com/contest/weekly-contest-197/problems/best-position-for-a-service-centre/
一家快遞公司希望在新城市建立新的服務(wù)中心裆甩。公司統(tǒng)計(jì)了該城市所有客戶在二維地圖上的坐標(biāo)魄缚,并希望能夠以此為依據(jù)為新的服務(wù)中心選址:使服務(wù)中心?到所有客戶的歐幾里得距離的總和最小?粱玲。
給你一個(gè)數(shù)組?positions?奢米,其中?positions[i] = [xi, yi]?表示第?i?個(gè)客戶在二維地圖上的位置,返回到所有客戶的?歐幾里得距離的最小總和 。
換句話說,請你為服務(wù)中心選址勾怒,該位置的坐標(biāo)?[xcentre, ycentre]?需要使下面的公式取到最小值:
與真實(shí)值誤差在?10^-5?之內(nèi)的答案將被視作正確答案。
================================================
本以為有公式的声旺,后來發(fā)現(xiàn)好像沒有笔链。。
然后解題思路就是腮猖,選一點(diǎn)鉴扫,然后不斷的向上下左右四個(gè)方向嘗試,不斷調(diào)整坐標(biāo)澈缺,看能不能得到更優(yōu)解坪创。。
起點(diǎn)可以用x,y的平均值
調(diào)整坐標(biāo)的步幅可以通過2分谍椅,某一次調(diào)整坐標(biāo)時(shí)误堡,如果不能找到最優(yōu)解則縮短步幅古话,步幅比精度小100倍時(shí)就滿足要求了