P1378 油滴扩展
程序员文章站
2022-06-01 21:32:34
...
题目描述 https://www.luogu.org/problemnew/show/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
说明:
1. 长方形的方向应该是沿着x y轴正放
2. 我这里采用的是获取下一个枚举得到所有的序列,实际上这个是没有dfs快的
3.但是有一个地方是需要注意的,就是如果这个油滴本身就在另外一个油滴的内部,那么我们就不能选择这个油滴,也就是当两个油滴之间的距离小于那个油滴的半径,我们就要把它变成0
4. 输出的时候,转化为整数输入,直接使用cout容易形成科学计数法
5 这里使用的是double 不能使用float 精度不够 另外 round的返回值是double,不是整数
6. printf("%0.0f")可以直接四舍五入
#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<sstream>
#include<string.h>
#include<map>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
double res=0;
#define N 8
#define Pi 3.1415926535
double x[N],y[N],seq[N],r[N];
double xb,yb,xa,ya;
//double fabs(double a)
//{return a>0?a:0-a;}
double tofind(int kk)
{
double imin1,imin2,imin;
int i=seq[kk];
imin1=min(fabs(x[i]-xa),fabs(x[i]-xb));
imin2=min(fabs(y[i]-ya),fabs(y[i]-yb));
imin=min(imin1,imin2);
for(int j,k=0;k<kk;k++)
{
j=seq[k];
double rr=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
if(rr<r[j])
{
imin=0;
}
else
{
imin=min(imin,rr-r[j]);
}
}
r[i]=imin;
return imin;
}
int main()
{
cin>>n;
cin>>xa>>ya>>xb>>yb;
int index=0;
while(index<n)
{
cin>>x[index]>>y[index];
seq[index]=index;
index++;
}
double imax=0,isum=0;
do
{
isum=0;
for(int i=0;i<n;i++)
{
double tr=tofind(i);
isum+=Pi*tr*tr;
//cout<<" "<<seq[i];
}
//cout<<isum<<endl;
imax=max(imax,isum);
}while(next_permutation(seq,seq+n));
res=fabs((yb-ya)*(xb-xa));
res-=imax;
//printf("%lf",res);
//cout<<res<<endl;
res=round(res);
//cout<<res<<endl;
printf("%d",int(res));
return 0;
}
另外dfs版本
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=10;
const double PI=3.1415926535;
bool s[maxn];
double x[maxn],y[maxn],r[maxn],xa,ya,xb,yb,ansmax;
int n;
double cal(int i)//这是计算当前的点的半径的函数
{
double s1=min(abs(x[i]-xa),abs(x[i]-xb));
double s2=min(abs(y[i]-ya),abs(y[i]-yb));
double ans=min(s1,s2);
for(int j=1;j<=n;j++)
if(i!=j&&s[j])
{
double d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
ans=min(ans,max(d-r[j],0.0));//如果距离都小于0了,那我还要你有何用
}
return ans;
}
void dfs(int k,double sum)
{
if(k>n)
{
ansmax=max(ansmax,sum);
return;
}
for(int i=1;i<=n;i++)
{
if(!s[i])
{
r[i]=cal(i);
s[i]=1;
dfs(k+1,sum+r[i]*r[i]*PI);
s[i]=0;
}
}
}
int main()
{
double ss;
scanf("%d",&n);
scanf("%lf%lf%lf%lf",&xa,&ya,&xb,&yb);
ss=abs(xa-xb)*abs(ya-yb);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
dfs(1,0);
printf("%d",int(ss-ansmax+0.5));//四舍五入
return 0;
}