Peienwu's Blog

Hello world

0%

[題解]Leetcode 1515 Best Position for a Service Centre

發表於 分類於 Valine：
文章字數： 1.8k 所需閱讀時間 ≈ 2 分鐘

1515 Best Position for a Service Centre

題目連結

這一題是模擬退火，非常酷，之前沒有寫過的東西。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#define eps 1e-6
#define ld long double
#define pdd pair<ld,ld>
#define x first
#define y second

class Solution {
public:
    pdd p[105];int n;
    
    ld dis_all(pdd mid){
        ld sum;
        for(int i = 0;i < n;i++){
            ld x = p[i].x - mid.x,y = p[i].y - mid.y;
            sum += sqrt(x * x + y * y);
        }
        return sum;
    }
    
    double getMinDistSum(vector<vector<int>>& pos) {
        n = pos.size();
        for(int i = 0;i < n;i++)p[i] = {pos[i][0],pos[i][1]};
        pdd cur = p[0];ld mid_dis = dis_all(p[0]);
        ld test_size = 100;
        ld dx[4] = {1.0,0.0,-1.0,0.0},dy[4] = {0.0,1.0,0.0,-1.0};
        bool flag = 0;
        while(test_size > eps){
            flag = 0;
            for(int i = 0;i < 4;i++){
                pdd newp = cur;
                newp.x += dx[i] * test_size;
                newp.y += dy[i] * test_size;
                ld new_dis = dis_all(newp);
                if(new_dis < mid_dis){
                    mid_dis = new_dis;
                    cur = newp;
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)test_size /= 2.0;
        }
        return mid_dis;
    }
};

換另外一種迭代方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#define eps 1e-8
#define ld long double
#define pdd pair<ld,ld>
#define x first
#define y second

class Solution {
public:
    pdd p[105];int n;
    
    ld dis_all(pdd mid){
        ld sum;
        for(int i = 0;i < n;i++){
            ld x = p[i].x - mid.x,y = p[i].y - mid.y;
            sum += sqrt(x * x + y * y);
        }
        return sum;
    }
    
    double getMinDistSum(vector<vector<int>>& pos) {
        srand(time(NULL));
        n = pos.size();
        for(int i = 0;i < n;i++)p[i] = {pos[i][0],pos[i][1]};
        pdd cur = p[0];ld mid_dis = dis_all(p[0]);
        ld test_size = 150.0;
        while(test_size > eps){
            pdd newp = cur;
            int temp = rand();
            newp.x += cos(temp) * test_size;
            newp.y += sin(temp) * test_size;
            ld new_dis = dis_all(newp);
            if(new_dis < mid_dis){
                mid_dis = new_dis;
                cur = newp;
            }
            else test_size *= 0.99;
        }
        return mid_dis;
    }
};