洛谷1378 油滴扩展

原题链接

爆搜水题，数据小，连剪枝也不用。
对于每个油滴，扩展的最大半径即是对圆心到(x)边界的距离、圆心到(y)边界的距离、与每个已经扩展的油滴圆心距离减去该油滴扩展的半径 取最小值，注意对(0)取(max)。

#include<cstdio>
#include<cmath>
using namespace std;
const int N = 10;
const double pi = 3.14159265358979323846;
struct dd{
	int x, y, pre, suc;
};
dd a[N];
int sta[N], sqlx, sqly, sqrx, sqry, n, tp;
double dis[N][N], edg[N], R[N], ma;
inline int re()
{
	int x = 0;
	char c = getchar();
	bool p = 0;
	for (; c < '0' || c > '9'; c = getchar())
		p |= c == '-';
	for (; c >= '0' && c <= '9'; c = getchar())
		x = x * 10 + c - '0';
	return p ? -x : x;
}
inline double minn(double x, double y)
{
	return x < y ? x : y;
}
inline double maxn(double x, double y)
{
	return x > y ? x : y;
}
inline double js(double x)
{
	return x < 0 ? -x : x;
}
inline void de(int x)
{
	a[a[x].pre].suc = a[x].suc;
	a[a[x].suc].pre = a[x].pre;
}
inline void con(int x)
{
	a[a[x].pre].suc = x;
	a[a[x].suc].pre = x;
}
void dfs(int x, double s)
{
	if (!(x ^ n))
		ma = maxn(ma, s);
	int i, j;
	double r;
	for (i = a[0].suc; i <= n; i = a[i].suc)
	{
		r = edg[i];
		for (j = 1; j <= tp; j++)
			r = minn(r, maxn(dis[i][sta[j]] - R[j], 0));
		sta[++tp] = i;
		R[tp] = r;
		de(i);
		dfs(x + 1, s + pi * r * r);
		con(i);
		tp--;
	}
}
int main()
{
	int i, j;
	n = re();
	sqlx = re();
	sqly = re();
	sqrx = re();
	sqry = re();
	for (i = 1, a[0].suc = 1, a[n + 1].pre = n; i <= n; i++)
	{
		a[i].x = re();
		a[i].y = re();
		a[i].pre = i - 1;
		a[i].suc = i + 1;
	}
	for (i = 1; i < n; i++)
		for (j = i + 1; j <= n; j++)
			dis[i][j] = dis[j][i] = sqrt(1.0 * (a[i].x - a[j].x) * (a[i].x - a[j].x) + 1.0 * (a[i].y - a[j].y) * (a[i].y - a[j].y));
	for (i = 1; i <= n; i++)
		edg[i] = minn(minn(js(a[i].x - sqlx), js(a[i].x - sqrx)), minn(js(a[i].y - sqly), js(a[i].y - sqry)));
	dfs(0, 0);
	printf("%.0f", js(sqlx - sqrx) * js(sqly - sqry) - ma);  
	return 0;
}