油滴扩展

链接

这题一看思路不难,就是将所有可能排列之后输出最小值即可

但需要注意几个点

1.π的精度要求比较高

2.存在包含问题,半径需要手动调整为0,否则输出负数

思路:

由于圆最大扩展到边界或和其他圆相切(包含则为点圆)

我们需要比较该点和边界的距离以及和其他圆的距离减去半径,取最小值就是该圆的半径

如果半径为负数,我们手动设置为0

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
struct node {
	double x, y, r;
};
void f(int x1,int y1,int x2,int y2,vector<pair<double,double>>oil_drop,vector<node>&oil,vector<bool>&visit,double& ans,int n) {
	if (oil.size() == n) {
		double sum = 0;
		for (int i = 0;i < n;i++) {
			sum += oil[i].r * oil[i].r * 3.1415926535;
		}
		ans =min((abs((x1 - x2) * (y1 - y2)) - sum),ans);
		return;
	}
	for (int i = 0;i < n;i++) {
		if (!visit[i]) {
			visit[i] = 1;
			double r_oil =1e8;
			for (int j = 0;j < oil.size();j++) {
				double dis = pow(pow((oil_drop[i].first - oil[j].x), 2) + pow((oil_drop[i].second - oil[j].y), 2), 0.5);
				r_oil = min(r_oil, dis - oil[j].r);
			}
			int x = oil_drop[i].first, y = oil_drop[i].second;
			int dis1 = abs(x - x1), dis2 = abs(x - x2), dis3 = abs(y - y1), dis4 = abs(y - y2);
			int min_dis_x = min(dis1, dis2), min_dis_y = min(dis3, dis4);
			r_oil = min(r_oil, min((double)min_dis_x, (double)min_dis_y));
			r_oil = max(r_oil, 0.0);
			oil.push_back({ oil_drop[i].first,oil_drop[i].second,r_oil });
			f(x1, y1, x2, y2, oil_drop, oil, visit, ans, n);
			visit[i] = 0;
			oil.pop_back();

		}
	}
}
int main() {
	int n;
	cin >> n;
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	vector<pair<double, double>>oil_drop(n);
	for (int i = 0;i < n;i++) {
		cin >> oil_drop[i].first >> oil_drop[i].second;
	}
	vector<node>oil;
	vector<bool>visit(n,0);
	double ans = 1e9;
	f(x1, y1, x2, y2, oil_drop, oil, visit, ans, n);
	cout <<fixed<<setprecision(0)<< ans;
}

时间复杂度:O(n!)

空间复杂度:O(n)