题目传送门
题目思路
思路就是DFS搜
注意几个特殊情况。。
目前还有三个点过不了，两个wa，一个出了负数（证明有逻辑问题）。暂定
#include <iostream>
#include <vector>
#include <math.h>
#define PI acos(-1)
using namespace std;
double ans = 2000.0 * 2000.0;
void dfs(vector<pair<int, int>> &v, vector<int> &vis, vector<double> &r, int x1, int y1, int x2, int y2, int n, int str)
{
if (str == n)
{
double temp = 0.0;
for (int i = 0; i < n; i++)
{
temp += r[i] * r[i] * PI;
}
temp = (abs(x2 - x1) * abs(y2 - y1)) - temp;
ans = min(ans, temp);
return;
}
for (int i = 0; i < n; i++)
{
if (vis[i] == 0)
{
vis[i] = 1;
double tt = (double)min(abs(v[i].first - x1), abs(v[i].second - y1));
tt = min(tt, (double)min(abs(v[i].first - x2), abs(v[i].second - y2)));
r[i] = tt;
for (int j = 0; j < n; j++)
{
if (i == j)
continue;
if (vis[j] == 0)
{
double te = sqrt((v[i].first - v[j].first) * (v[i].first - v[j].first) + (v[i].second - v[j].second) * (v[i].second - v[j].second));
if (0.001 <= tt - te)
r[i] = max(r[i], te);
}
else if (vis[j] == 1)
{
double t = sqrt((v[i].first - v[j].first) * (v[i].first - v[j].first) + (v[i].second - v[j].second) * (v[i].second - v[j].second));
if (t <= r[j])
r[i] = 0.0;
else
r[i] = min(r[i], t - r[j] > 0.001 ? t - r[j] : 0.0);
}
}
dfs(v, vis, r, x1, y1, x2, y2, n, str + 1);
r[i] = 0.0;
vis[i] = 0;
}
}
}
int main()
{
int n;
cin >> n;
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1 += 1000;
y1 += 1000;
x2 += 1000;
y2 += 1000;
vector<pair<int, int>> v(n);
vector<int> vis(n, 0);
vector<double> r(n, 0.0);
for (int i = 0; i < n; i++)
{
cin >> v[i].first >> v[i].second;
v[i].first += 1000;
v[i].second += 1000;
}
dfs(v, vis, r, x1, y1, x2, y2, n, 0);
printf("%.0lf", ans);
return 0;
}二做;
草了，妈的，多此一举的代码，去掉下面的代码就过了：
if (vis[j] == 0)
{
double te = sqrt((v[i].first - v[j].first) * (v[i].first - v[j].first) + (v[i].second - v[j].second) * (v[i].second - v[j].second));
if (0.001 <= tt - te)
r[i] = max(r[i], te);
}因为最大就是边界，不可能再大了，因此只需要按照已经扩散的去减小就行了，我为啥要去判断继续增大。。。我是不是傻逼。。
AC代码
#include <iostream>
#include <vector>
#include <math.h>
#define PI acos(-1)
using namespace std;
double ans = 2000.0 * 2000.0;
void dfs(vector<pair<int, int>> &v, vector<int> &vis, vector<double> &r, int x1, int y1, int x2, int y2, int n, int str)
{
if (str == n)
{
double temp = 0.0;
for (int i = 0; i < n; i++)
{
temp += r[i] * r[i] * PI;
}
temp = (abs(x2 - x1) * abs(y2 - y1)) - temp;
ans = min(ans, temp);
return;
}
for (int i = 0; i < n; i++)
{
if (vis[i] == 0)
{
vis[i] = 1;
double tt = (double)min(abs(v[i].first - x1), abs(v[i].second - y1));
tt = min(tt, (double)min(abs(v[i].first - x2), abs(v[i].second - y2)));
r[i] = tt;
for (int j = 0; j < n; j++)
{
if (i == j)
continue;
if (vis[j] == 1)
{
double t = sqrt((v[i].first - v[j].first) * (v[i].first - v[j].first) + (v[i].second - v[j].second) * (v[i].second - v[j].second));
if (t <= r[j])
r[i] = 0.0;
else
r[i] = min(r[i], t - r[j]);
}
}
dfs(v, vis, r, x1, y1, x2, y2, n, str + 1);
r[i] = 0.0;
vis[i] = 0;
}
}
}
int main()
{
int n;
cin >> n;
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1 += 1000;
y1 += 1000;
x2 += 1000;
y2 += 1000;
vector<pair<int, int>> v(n);
vector<int> vis(n, 0);
vector<double> r(n, 0.0);
for (int i = 0; i < n; i++)
{
cin >> v[i].first >> v[i].second;
v[i].first += 1000;
v[i].second += 1000;
}
dfs(v, vis, r, x1, y1, x2, y2, n, 0);
printf("%.0lf", ans);
return 0;
}