欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}

 

相关标签: double