#include <bits/stdc++.h>
using namespace std;
long long n;
int xA, yA, xB, yB;
int dots[7][2];
double rs[7];
double ans;
int f;
double distance(double x1, double y1, double x2, double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void update()
{
double total;
for (int i=0; i<n; i++)
total += rs[i]*rs[i]*M_PI;
ans = max(ans, total);
}
void dfs(int state)
{
if (state==f)
{
update();
return;
}
for (int i=0; i<n; i++)
{
if (((1<<i) & state)==0)
{
int x=dots[i][0], y=dots[i][1];
// 到边框的最大半径
double radius = 114514.0;
radius = min(abs(xA-x*1.0), radius);
radius = min(abs(xB-x*1.0), radius);
radius = min(abs(yA-y*1.0), radius);
radius = min(abs(yB-y*1.0), radius);
// 到各个油滴的最大半径
for (int j=0; j<n; j++)
{
if (i==j) continue;
if ((state>>j)&(1)==0) continue;
double d = distance(x, y, dots[j][0], dots[j][1]);
radius = min(radius, max(d-rs[j], 0.0));
if (radius<0) radius=0;
}
rs[i] = radius;
printf("%lf\n", rs[i]); // DEBUG
dfs(state|(1<<i));
}
}
}
int main()
{
cin >> n;
f = (1<<n)-1;
ans = 0;
cin >> xA >> yA >> xB >> yB;
xA += 1000;
yA += 1000;
xB += 1000;
yB += 1000;
for (int i=0; i<n; i++)
{
int x, y;
cin >> x >> y;
dots[i][0] = x+1000;
dots[i][1] = y+1000;
}
dfs(0);
// printf("%lf\n", ans);
cout << abs(xA-xB)*abs(yA-yB)-(int)(ans+0.5) << endl;
return 0;
}
以上的代码,在我的电脑上可以过样例,但是在洛谷在线 IDE 上样例输出 47。
当然这还不是最玄学的地方,无论在我的电脑或是洛谷 IDE 上,如果将dfs()中标着// DEBUG的那行调试输出删掉,输入样例的输出就会变成-2147483548或-1。
样例输入
2
20 0 10 10
13 3
17 7
我的电脑,有调试语句
3.000000
2.656854
2.656854
3.000000
50
洛谷在线 IDE,有调试语句
3.000000
2.656854
2.656854
3.000000
47
删掉调试语句
在线 IDE
-2147483548
本地
-1