Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
在一个长方形框子里，最多有N（0≤N≤6）个相异的点。在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这N个 点上放置
油滴，才能使放置完毕后所有油滴占据的体积最大呢？（不同的油滴不会相互融合）
注：圆的面积公式 V=pi*r*r,其中r为圆的半径。
【输入格式】
第一行一个整数N。
第二行为长方形边框一个顶点及其对角顶点的坐标，x ,y ,x’,y’。
接下去N行，每行两个整数xi,yi,表示盒子内N个点的坐标。
以上所有的整数都在[-1000,1000]内。
【输出格式】
一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）。
Sample Input
2
0 0 10 10
3 3
7 7
Sample Output
50
【题解】
只要把每一种扩展油滴的顺序都枚举出来就可以了。
要考虑的东西:
1.两点之间的距离和其他圆的半径
2.对边界情况的判断
这两个情况都考虑到之后。就能求出当前枚举的这个点能扩展多大的半径了。
如果有某个点被覆盖到另外一个圆内的情况。
则把这个点的扩展圆的半径设为0；
当圆的个数达到N时。尝试更新一下所有圆的面积的最大值。
最后用矩形的面积减去这个最大值就可以了。
【代码】
#include <cstdio> #include <stdlib.h> #include <cstring> #include <cmath> struct point //这是用于输入n个扩展点 { int x,y; }; struct circle //这是用于记录扩展圆的信息。即它的圆心坐标和圆的半径。 { int x,y; double r; }; double ma = 0; int n,xx0,yy0,xx1,yy1; point a[7]; circle b[7] = {0}; bool bo[7]; //用于进行全排列的判重。 void input_data() { memset(bo,true,sizeof(bo)); //一开始所有的油滴都可以进行扩展 scanf("%d",&n); scanf("%d%d%d%d",&xx0,&yy0,&xx1,&yy1); //输入矩形框的信息。 for (int i = 1;i <= n;i++) //输入n个扩展点 scanf("%d%d",&a[i].x,&a[i].y); } double min(double a,double b) //返回a和b中的较小值。 { return a>b?b:a; } void sear_ch(int now,int c_num) //当前要扩展第now个点。扩展完后它就是第c_num个圆。 { double minr = 2100000000; for (int i = 1;i <= c_num-1;i++) //要根据前c_num-1个圆来获取这个圆能扩展的最大半径 { if (b[i].r > 0) { double dis; dis = (b[i].x-a[now].x)*(b[i].x-a[now].x)+(b[i].y-a[now].y)*(b[i].y-a[now].y); dis = sqrt(dis); minr = min(minr,dis-b[i].r); //因为不能碰到它们，所以是求最小值 } } double aa = a[now].x-xx0; //以下这一段是用来防止圆超过边界的情况。 double bb = a[now].x-xx1; //还要根据这些信息来获取正确的扩展圆的半径。 if (aa<0) aa=-aa; if (bb<0) bb=-bb; aa = min(aa,bb); minr = min(minr,aa); aa = a[now].y-yy0; bb = a[now].y-yy1; if (aa <0) aa=-aa; if (bb<0) bb=-bb; aa = min(aa,bb); minr = min(minr,aa); if (minr < 0) //如果这个点被其他圆所覆盖。所得到的圆的半径会是负数。这时候就不要扩展。设为0 b[c_num].r = 0; else b[c_num].r = minr; b[c_num].x = a[now].x; //记录下这个圆的圆心坐标 b[c_num].y = a[now].y; if (c_num == n) //如果n个圆都已经出来了则累加它们的面积和。 { double s = 0; for (int i = 1;i<=n;i++) s+=3.1415926*b[i].r*b[i].r; if (s > ma) //如果面积比原来记录的最大值更大。则更新。 ma = s; return; } for (int i = 1;i <= n;i++) //要进行全排列。即枚举所有的扩展顺序。 if (bo[i]) //不同的扩展顺序会有不一样的结果。 { bo[i] = false; sear_ch(i,c_num+1); bo[i] = true; } } void get_ans() { for (int i = 1;i <= n;i++) //在递归的外面同样要为全排列进行一次for循环。 if (bo[i]) { bo[i] = false; sear_ch(i,1); bo[i] = true; } } void output_ans() { int xx = xx1-xx0,yy = yy1-yy0; double temp = xx*yy; if (temp < 0) //最后输出剩余的面积即可。 temp=-temp; temp = temp - ma; printf("%.lf",temp); } int main() { //freopen("F:\rush.txt","r",stdin); input_data(); get_ans(); output_ans(); return 0; }