题目描述
在一个长方形框子里，最多有N（0≤N≤6）个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这N个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不同的油滴不会相互融合）
注：圆的面积公式V=pirr，其中r为圆的半径。
输入输出格式
输入格式：
第1行一个整数N。
第2行为长方形边框一个顶点及其对角顶点的坐标，x,y,x’,y’。
接下去N行，每行两个整数xi,yi，表示盒子的N个点的坐标。
以上所有的数据都在[-1000，1000]内。
输出格式：
一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）
输入输出样例
输入样例#1：
2
20 0 10 10
13 3
17 7
输出样例#1：
50
解释:
---------题解(Gelphue),老天爷都找不到更良心的题解了---------
对于这道题(好久没写搜索了呢),对答案起决定性因素的是点拓展的顺序(DFS就是在搜索TA),其次就是对题中各种要求的处理,列表:
-
1.对于所给长方形,为了统一形式,设点kup为左上角,lap为右下角,且横坐标为Y,纵坐标为X(横坐标为j,纵坐标为i);处理方式为:
cin >> n; cin >> kup.x >> kup.y >> lap.x >> lap.y; if (kup.x > lap.x) swap(kup.x, lap.x);//保证左上角的横坐标严格小于右下角的横坐标 if (kup.y > lap.y) swap(kup.y, lap.y);//保证左上角的纵坐标严格小于右下角的纵坐标 -
2.对于输入的N个点以及左上,右下坐标,全部自减点kup(坐上坐标),以使长方形的左上角与坐标原点重合,即所有点都在第四象限类,每一的点拓展出去的半径r初始化为0,处理方案为:
for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y, a[i].x -= kup.x, a[i].y -= kup.y, a[i].r = 0; lap.x -= kup.x, lap.y -= kup.y; -
3.预处理每两个点之间的距离,用二维数组贮存,处理方案为:
for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) dist[i][j] = sqrt(pow(a[i].x - a[j].x, 2) + pow(a[i].y - a[j].y, 2)), dist[j][i] = dist[i][j];//a[i]到a[j] 和 a[j]到a[i] 的距离相同 } -
4.用DOUBLE anso表示在不同的拓展顺序中能得到的最大半径和(为 a[1].r^2+a[2].r^2+...+a[N].r^2),输出则用长方形面积(lap.xlap.y)减去总共圆的面积(为 ansoPi),处理方案为(推导过程就不必说了吧):
dfs(1); cout << (int)(lap.x*lap.y - floor(anso*Pi + 1.0 / 2)) << endl; -
5.先上一份dfs()的代码:
void dfs(int d) { if (d > n) { double tem_as = 0.0;//统计在这种顺序下的半径平方和 for (int i = 1; i <= n; i++) tem_as += a[i].r_R;//为了优化时间复杂度,把a[i].r*a[i].r单独作为一个成员变量(a[i].r_R) anso = max(anso, tem_as);//更性较大值 } for (int i = 1; i <= n; i++) if (!use[i])//还没有被搜过 { use[i] = 1; {//以下高能,稍后解释*1 a[i].r = min(min(a[i].x, lap.x - a[i].x), min(a[i].y, lap.y - a[i].y)); for (int k = 1; k <= n; k++) if (use[k]&& k!=i) { a[i].r = min(a[i].r, dist[i][k] - a[k].r); } if (a[i].r < 0) a[i].r = 0; } a[i].r_R = a[i].r*a[i].r;//更新半径平方 dfs(d + 1);//进行下一层搜索 use[i] = 0; } } /*1:解释在这儿:对于正在搜的点,要满足a[i]在长方形以内,则需要满足 a[i].x-a[i].r>=0, a[i].y-a[i].r>=0, a[i].x+a[i].r<=lap.x, a[i].y+a[i].r<+lap.y. 所以有了这一句话: a[i].r = min(min(a[i].x, lap.x - a[i].x), min(a[i].y, lap.y - a[i].y)); ;然后就要找所有已经找过的点(a[k])一一和a[i]进行比较,其中a[i].r必须要满足: a[i].r+a[k].r<=dist[i][k], 至于为什么,这里扔一张图 */
好了,综上所述,完整的代码在这里
// 动态规划专题(zx).cpp : 定义控制台应用程序的入口点。
//Strengthen self without stopping, and hold world with virtue
//
#include "stdafx.h"
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Pi (double)3.14159265358
#define redef ios::sync_with_stdio(false),cout.tie(NULL);
int n;
double dist[7][7];
double anso=0;
bool use[7];
struct pl
{
double x, y, r;
double r_R;//r_R=:r*r;
bool operator < (const pl&oth)const
{
return (x <= oth.x && y <= oth.y);
}
}a[7], kup, lap;
void dfs(int d)
{
if (d > n)
{
double tem_as = 0.0;
for (int i = 1; i <= n; i++)
tem_as += a[i].r_R;
anso = max(anso, tem_as);
}
for (int i = 1; i <= n; i++)
if (!use[i])
{
use[i] = 1;
{
a[i].r = min(min(a[i].x, lap.x - a[i].x), min(a[i].y, lap.y - a[i].y));
for (int k = 1; k <= n; k++)
if (use[k]&& k!=i)
{
a[i].r = min(a[i].r, dist[i][k] - a[k].r);
}
if (a[i].r < 0) a[i].r = 0;
}
a[i].r_R = a[i].r*a[i].r;
dfs(d + 1);
use[i] = 0;
}
}
int main()
{
redef cin >> n;
cin >> kup.x >> kup.y >> lap.x >> lap.y;
{
if (kup.x > lap.x) swap(kup.x, lap.x);
if (kup.y > lap.y) swap(kup.y, lap.y);
}
for (int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y,
a[i].x -= kup.x,
a[i].y -= kup.y,
a[i].r = 0;
lap.x -= kup.x, lap.y -= kup.y;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < i; j++)
dist[i][j] = sqrt(pow(a[i].x - a[j].x, 2) + pow(a[i].y - a[j].y, 2)),
dist[j][i] = dist[i][j];
}
dfs(1);
cout << (int)(lap.x*lap.y - floor(anso*Pi + 1.0 / 2)) << endl;
return 0;
}