社区讨论
0分求调
P1378油滴扩展参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @losos2y5
- 此快照首次捕获于
- 2023/11/10 22:01 2 年前
- 此快照最后确认于
- 2023/11/11 08:54 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10e6 + 45;
const int pi = 3.14159265;
int xa, ya, xb, yb, n;
double ans;
bool fl[maxn];
struct node{
int x, y;
double r;
}e[maxn];
void dfs (int i, double sum)
{
if (i == n + 1) ans = max (ans, sum);
for (int j = 1; j <= n; j ++)
{
if (!fl[j])
{
int f = 0;
for (int k = 1; k <= n; k ++)
{
if (fl[k] == false && e[j].r >= sqrt((e[j].x - e[k].x) * (e[j].x - e[k].x) + (e[j].y - e[k].y) * (e[j].y - e[k].y) ))
{
fl[j] = true;
f = 1;
dfs (i + 1, sum);
f = 0;
}
}
if (f == 1) continue;
fl[i] = true;
e[j].r = min (abs(e[j].x - xa), abs(e[j].x - xb));
double minn = min (abs(e[j].y - ya), abs(e[j].y - yb));
e[j].r = min (e[i].r, minn);
for (int k = 1; k <= n; k ++)
{
if (j != k && fl[k])
{
double dd = sqrt ((e[j].x - e[k].x) * (e[j].x - e[k].x) + (e[j].y - e[k].y) * (e[j].y - e[k].y) );
e[j].r = min (e[j].r, dd - e[j].r);
}
}
dfs (i + 1, sum + pi * e[j].r * e[j].r);
e[j].r = 0;
fl[j] = false;
}
}
}
int main()
{
cin >> n;
cin >> xa >> ya >> xb >> yb;
xa += 1000, xb += 1000, ya += 1000, yb += 1000;
for (int i = 1; i <= n; i ++)
{
int a, b;
cin >> a >> b;
e[i].x = a + 1000;
e[i].y = b + 1000;
}
double ss = abs(xa - xb) * abs(ya - yb);
dfs (1, 0.0);
cout << floor(ss - ans - 1) ;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...