题目描述
在二维平面上,寻找一个最优解的点;模拟退火找就完事了
跟另一道题差不多的套路 星星还是树
计算坐标(x,y)电源到其它各个栅栏的距离之和
题目说了,所有围栏都与坐标轴平行
枚举各个栅栏的坐标,一个栅栏和电源点关系有三种情况,下图解释了
设电源坐标为(x, y),栅栏的两个端点的坐标是(n, m) (a, b)
三种情况.png
上面的图片 应该是点到线段的距离,打错了打成了点到直线距离
代码 结合模拟退火
#include <iostream>
#include <cmath>
const double eps = 1e-6;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
struct line{
int x, y, a, b;
}li[200];
double xx, yy, t;
using namespace std;
int f;
double getdist(double x, double y) {
double sum = 0;
for (int i = 0; i < f; i++) {//枚举所有的线段 算距离
double n = li[i].x, m = li[i].y, a = li[i].a, b = li[i].b;
//三种情况 题目说 栅栏必定与坐标轴平行
if (n <= x && x <= a) sum += fabs(y - m);//与X轴平行的栅栏 m = b
else if (m <= y && y <= b) sum += fabs(x - n);//与y轴平行的栅栏
else { //第三种情况
double v1, v2;
n -= x, m -= y, a -= x, b -= y;
v1 = sqrt(n * n + m * m);
v2 = sqrt(a * a + b * b);
sum += min(v1, v2);
}
}
return sum ;
}
int main() {
cin >> f;
for (int i = 0; i < f; i++) cin >> li[i].x >> li[i].y >> li[i].a >> li[i].b;
double ans = 1e10;
xx = li[0].x;
yy = li[0].y;
t = 1;
while (t > eps) {
int flag = 0;
for (int i = 0; i < 4; i++) {
double nx = xx + t * dx[i], ny = yy + t * dy[i];
double tmp = getdist(nx, ny);
if (tmp < ans) {
ans = tmp;
xx = nx;
yy = ny;
flag = 1;
}
}
if (flag == 0) t *= 0.98;
}
printf("%.1f %.1f %.1f", xx, yy, ans);
return 0;
}