求助,只有三十分
查看原帖
求助,只有三十分
759274
Stevehim楼主2022/12/2 07:46
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#define maxn 20
using namespace std;
double pi = 3.1415926;

// 向 面对油滴编程的大佬致敬
struct node {
	double x;
	double y;
	double min_wall; //与长方形四条边的最小值
} a[maxn];
double dis[maxn][maxn]; //两点之间的距离

int book[maxn] = {0};
int n;
double ans = 10000009;
double wall_x1, wall_x2, wall_y1, wall_y2;
double square;

double work_dis(double x1, double x2, double y1, double y2) { //计算两点之间的欧几里得距离
	return sqrt(abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2));
}

double work_circle(double r) {
	return (r * r * pi); //圆形公式
}

void dfs(int k, double sum) {
	//边界条件
	if (k > n) {
		ans = min(ans, sum);
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!book[i]) { //没被访问,可以列举
			book[i] = 1; // 先把自身设为访问,提示:1是访问过的状态,2是可以擦除的状态
			double mi_dis = a[i].min_wall;
			for (int j = 0; j < n; j++) {
				if (j == i || book[j] == 1) {
					continue;
				}
				if (dis[i][j] - mi_dis < 0) {
					mi_dis = dis[i][j];
				}
			}
			for (int j = 0; j < n; j++) {
				if (j == i || book[j] == 1) {
					continue;
				}
				dis[i][j] -= mi_dis;
				dis[j][i] -= mi_dis;
				if (dis[i][j] <= 0) {
					book[j] = 2;
				}
			}
			dfs(k + 1, sum - work_circle(mi_dis)); //开始dfs
			for (int j = 0; j < n; j++) {
				if (j == i) {
					continue;
				}
				if (book[j] == 2) {
					dis[i][j] += mi_dis;
					dis[j][i] += mi_dis;
					if (dis[i][j] > 0) {
						book[j] = 0; //标记给改回来
					}
				} else {
					continue;
				}

			}
			book[i] = 0;
		}
	}
	return;
}

int main() {
	cin >> n;
	cin >> wall_x1 >> wall_y1 >> wall_x2 >> wall_y2;
	wall_x1 += 1000;
	wall_x2 += 1000;
	wall_y1 += 1000;
	wall_y2 += 1000;//进行处理
	square = abs(wall_x1 - wall_x2) * abs(wall_y1 - wall_y2);
	for (int i = 0; i < n; i++) {
		cin >> a[i].x >> a[i].y;
		a[i].x += 1000;
		a[i].y += 1000;
		double mi_x = min(abs(a[i].x - wall_x1), abs(a[i].x - wall_x2)); //将x最小求出
		double mi_y = min(abs(a[i].y - wall_y1), abs(a[i].y - wall_y2)); //将y最小求出
		a[i].min_wall = min(mi_x, mi_y);
	}
	//输入完成后计算距离
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dis[i][j] = work_dis(a[i].x, a[j].x, a[i].y, a[j].y); //计算距离
		}
	}
	dfs(1, square);
	cout << round(ans);
	return 0;
}

2022/12/2 07:46
加载中...