油滴扩展
题目描述
在一个长方形框子里,最多有 \(N\) 个相异的点,在其中任何一个点上放一个很小的油滴,那么这个油滴会一直扩展,直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这 \(N\) 个点上放置油滴,才能使放置完毕后所有油滴占据的总面积最大呢?(不同的油滴不会相互融合)
注:圆的面积公式 \(S = \pi r^2\),其中 \(r\) 为圆的半径。
输入格式
第一行,一个整数 \(N\)。
第二行,四个整数 \(x, y, x’, y’\),表示长方形边框一个顶点及其对角顶点的坐标。
接下来 \(N\) 行,第 \(i\) 行两个整数 \(x_i, y_i\),表示盒子内第 \(i\) 个点的坐标。
输出格式
一行,一个整数,长方形盒子剩余的最小空间(结果四舍五入输出)。
样例 #1
样例输入 #1
2
20 0 10 10
13 3
17 7
样例输出 #1
50
提示
对于 \(100\%\) 的数据,\(1 \le N \le 6\),坐标范围在 \([-1000, 1000]\) 内。
问题分析
本题实际上是一个全排列问题,可以使用dfs,搜索所有排列,找到是的覆盖面积最大的排列
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double pi = 3.1415926535;
const int maxn = 10;
bool flag[maxn];
double ansum;
double x[maxn], y[maxn], r[maxn], xa, ya, xb, yb;
int n;
double cal(int i)//这是计算当前的点的半径的函数
{
double s1 = min(abs(x[i] - xa), abs(x[i] - xb));
double s2 = min(abs(y[i] - ya), abs(y[i] - yb));
double ans = min(s1, s2);
for (int j = 1; j <= n; j++) {
if (i != j && flag[j])
{
double d = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
//d-r为负数的时候代表该点已经被其他油滴覆盖,则不用延申
ans = min(ans, max(d - r[j], 0.0));
}
return ans;
}
}
void dfs(int num, double sum) {
//调用dfs(0,0)
if (num == n) {
ansum = max(ansum, sum);
return;
}
for (int i = 1; i <= n; i++) {
if (!flag[i]) {
r[i] = cal(i);
flag[i] = 1;
dfs(num + 1, sum + r[i] * r[i] * pi);
//回溯
flag[i] = 0;
}
}
}
int main()
{
double ss;
scanf("%d", &n);
scanf("%lf%lf%lf%lf", &xa, &ya, &xb, &yb);
ss = abs(xa - xb) * abs(ya - yb);
for (int i = 1; i <= n; i++){
scanf("%lf%lf", &x[i], &y[i]);
}
dfs(0, 0);
printf("%d", int(ss - ansum + 0.5));//四舍五入
return 0;
}
没有回复内容