【搜索】洛谷 P1378 油滴扩展

题目描述

在一个长方形框子里，最多有N（0≤N≤6）个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这N个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不同的油滴不会相互融合）

注：圆的面积公式V=pi*r*r，其中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

代码

#include
#include
#include
#include
#include
#include
using namespace std;
double xx1,yy1,xx2,yy2,r[10],ans,pi=acos(-1);
int a[20],n;
bool b[10];
struct node{double x;double y;
};
node point[10];
bool judge(int k)
{if(point[k].xxx2||point[k].yyy2)return true;return false;
}
void search()
{double s=0;memset(r,0,sizeof(r));for(int i=1;i<=n;i++){if(judge(a[i])){r[i]=0;continue;}double tmp=1e9+7;         tmp=min(tmp,abs(point[a[i]].x-xx1));tmp=min(tmp,abs(point[a[i]].y-yy1));tmp=min(tmp,abs(xx2-point[a[i]].x));tmp=min(tmp,abs(yy2-point[a[i]].y));for(int j=1;jdouble temp=sqrt((double)(point[a[i]].x-point[a[j]].x)*(point[a[i]].x-point[a[j]].x)+(double)(point[a[i]].y-point[a[j]].y)*(point[a[i]].y-point[a[j]].y))-r[j];if(tempif(tmp<0)r[i]=0;else r[i]=tmp;s+=(double)pi*r[i]*r[i];}ans=max(ans,s);
}
void arrange(int k)
{for(int i=1;i<=n;i++){if(b[i]){a[k]=i;b[i]=false;if(k==n)search();else arrange(k+1);b[i]=true;}}
}
int main()
{scanf("%d",&n);scanf("%lf%lf%lf%lf",&xx1,&yy1,&xx2,&yy2);if(xx1>xx2)swap(xx1,xx2);if(yy1>yy2)swap(yy1,yy2);for(int i=1;i<=n;i++)scanf("%lf%lf",&point[i].x,&point[i].y);memset(b,true,sizeof(b));arrange(1);double sq=(double)(abs(xx1-xx2)*abs(yy1-yy2));printf("%.0lf",sq-ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！