P1378 油滴扩展 题解

· · 题解

P1378 油滴扩展 题解

思路解析

这里提供一种抽象的模拟退火做法。可以发现答案只跟顺序有关，发现正好符合模拟退火的条件，于是正常使用模拟退火即可。

所谓模拟退火实际上就是随机化，正常的全排列是枚举每一种交换的情况，而模拟退火就是随机化随机的两个位置，如果更优则直接更新答案，若不优则只用一定概率转移。

code

#include<bits/stdc++.h>
using namespace std;
mt19937 rd(time(0));
const int N = 8;
const double pai = 3.1415926;
const unsigned int RDMX = (unsigned)-1;
int n, sx, sy, ex, ey, ox[N], oy[N];
double r[N], ans = 0;
double dis(double xa, double ya, double xb, double yb) {
    return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
}
double get() {
    double sum = 0;
    for(int i = 1; i <= n; i++) {
        r[i] = min({abs(sx - ox[i]), abs(ex - ox[i]), abs(sy - oy[i]), abs(ey - oy[i])});
        for(int j = 1; j < i; j++) {
            if(dis(ox[i], oy[i], ox[j], oy[j]) > r[j]) r[i] = min(r[i], dis(ox[i], oy[i], ox[j], oy[j]) - r[j]);
            else r[i] = 0;
        }
        sum += r[i] * r[i] * pai;
    }
    return (double)abs(ex - sx) * abs(ey - sy) - sum;
}
void sa() {
    double t = 1000;
    while(t > 1e-12) {
        int a = rd() % n + 1, b = rd() % n + 1;
        swap(ox[a], ox[b]); swap(oy[a], oy[b]);
        double w = get();
        if(w < ans) ans = w;    //比当前答案更优
        else if(exp((double)(ans - w) / t) * RDMX < (double)rd()) { //不优，以一定概率转移
            swap(ox[a], ox[b]); swap(oy[a], oy[b]);
        }
        t *= 0.9996;
    }
}
int main() {
    cin >> n >> sx >> sy >> ex >> ey;
    for(int i = 1; i <= n; i++) {
        cin >> ox[i] >> oy[i];
    }
    ans = get();
    while((double)clock() / CLOCKS_PER_SEC <= 0.9) sa();
    printf("%.0lf", ans);
    return 0;
}