题目描述

Leetcode第197周赛最后一题

C++ 代码

class Solution {
#define rep(i,l,r) for(int i=l;i<=r;i++)

double getsum(vector<vector<int>>& positions,double xx,double yy) {
    double sum=0;
    int n=positions.size();
    rep(i,0,n-1) {
        sum+=sqrt((xx-positions[i][0])*(xx-positions[i][0])+(yy-positions[i][1])*(yy-positions[i][1]));
    }
    return sum;
}
public:
    double getMinDistSum(vector<vector<int>>& positions) {
        int n=positions.size();
        srand(time(NULL));
        double Ans=1e18,x=positions[0][0],y=positions[0][1];
        double now=Ans,tmp;
        double eps=1e-6;
        if (n==1) return 0.0000;
        double t=23333;
        while(t>eps) {
            int flag=0;
            rep(i,-1,1) {
                rep(j,-1,1) {
                    double nx=x+t*i,ny=y+t*j;
                    tmp=getsum(positions,nx,ny);
                    if (tmp<Ans) x=nx,y=ny,Ans=tmp,flag=1;
                }
            }
            if (!flag) t/=2; 
        }
        return Ans;
    }
};