算法1
(模拟退火) $O(tnlogT)$
代价函数为点到各个栅栏最短距离和,点$(x,y)$到栅栏$(x_1,y_1,x_2,y_2)$最短距离分三种情况:
1. $x$在$x_1$和$x_2$范围内,最短距离是$y$在$Y$轴上到$y_1$和$y_2$的垂直距离.
2. $y$在$y_1$和$y_2$范围内,最短距离是$x$在$X$轴上到$x_1$和$x_2$的水平距离.
3. 不在上述两种情况则最短距离是点到栅栏两端点距离最小值.
时间复杂度
t次模拟退火,一次模拟退火设置温度T$O(nlogT)$复杂度,合计$O(tnlogT)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
double rand(double l, double r){
return (double)rand() / RAND_MAX * (r - l) + l;
}
double getd(double x1, double y1, double x2, double y2){
double dx = x1 - x2;
double dy = y1 - y2;
return sqrt(dx * dx + dy * dy);
}
double mind(int x1, int y1, int x2, int y2, double x, double y){
if(x1 <= x and x <= x2){
return min(abs(y1 - y), abs(y2 - y));
}
if(y1 <= y and y <= y2){
return min(abs(x1 - x), abs(x2 - x));
}
return min(getd(x1,y1,x,y), getd(x2,y2,x,y));
}
vector<vector<int>> a;
int n;
double rex, rey, ans;
const int inf = 1e9;
double getc(double x, double y){
double re = 0;
for(int i = 0; i < n; ++i){
double d = mind(a[i][0], a[i][1], a[i][2], a[i][3], x, y);
// cout << "d = " << d << "\n";
re += d;
}
if(re < ans){
ans = re;
rex = x;
rey = y;
// cout << rex << " " << rey << " " << ans << "\n";
}
return re;
}
void sa(){
double x = rand(0, 100), y = rand(0, 100);
for(double t = 1e2; t > 1e-4; t *= 0.9){
double c1 = getc(x, y);
double nx = x + rand(-t, t), ny = y + rand(-t, t);
double c2 = getc(nx, ny);
double dt = c2 - c1;
if(exp(-dt / t) > rand(0, 1)){
x = nx;
y = ny;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
ans = inf;
srand((unsigned)time(NULL));
for(int i = 0; i < n; ++i){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
a.push_back({x1, y1, x2, y2});
}
for(int i = 0; i < 200; ++i) sa();
cout << setiosflags(ios::fixed) << setprecision(1);
cout << rex << " " << rey << " " << ans << "\n";
// cout << getc(1, 1.6) << "\n";
}
建议更正一下hh
可以去看一下正解的代码(题解区里面有一些代码是正解的,概率都是100%因为全程没有使用rand啊)
这种写法是有误的,现在能通过的概率非常低