洛谷P1378 油滴扩展(搜索)

时间:2022-12-31 21:56:35

洛谷P1378 油滴扩展

直接暴力搜索更新答案就可以了。

时间复杂度为 \(O(n!)\) 。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm> using namespace std; const int maxn = 10;
const double pi = acos(-1.0);
int vis[maxn];
double x[maxn], y[maxn], r[maxn];
double xa, xb, ya, yb, tot, ans;
int n; double cal(int i)
{
double ret = min(min(fabs(x[i] - xa), fabs(x[i] - xb)), min(fabs(y[i] - ya), fabs(y[i] - yb)));
for(int j = 1; j <= n; j++){
if(i != j && vis[j]){
double d = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
ret = min(ret, max(d - r[j], 0.0));
}
}
return ret;
}
void dfs(int k, double sum)
{
if(k > n){
ans = max(ans, sum);
return;
}
for(int i = 1; i <= n; i++){
if(!vis[i]){
r[i] = cal(i);
vis[i] = 1;
dfs(k + 1, sum + r[i] * r[i] * pi);
vis[i] = 0;
}
}
}
int main()
{
scanf("%d", &n);
scanf("%lf%lf%lf%lf", &xa, &ya, &xb, &yb);
for(int i = 1; i <= n; i++){
scanf("%lf%lf", &x[i], &y[i]);
}
tot = fabs(xa - xb) * fabs(ya - yb);
ans = 0.0;
dfs(1, 0);
printf("%d\n", (int)(tot - ans + 0.5));
return 0;
}