洛谷 P1378 油滴扩展 改错
2024-09-24 16:40:21
P1378 油滴扩展
题目描述
在一个长方形框子里,最多有\(N(0≤N≤6)\)个相异的点,在其中任何一个点上放一个很小的油滴,那么这个油滴会一直扩展,直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这\(N\)个点上放置油滴,才能使放置完毕后所有油滴占据的总面积最大呢?(不同的油滴不会相互融合)
输入输出格式
输入格式:
第1行一个整数N。
第2行为长方形边框一个顶点及其对角顶点的坐标,\(x,y,x’,y’\)。
接下去\(N\)行,每行两个整数\(x_i,y_i\),表示盒子的\(N\)个点的坐标。
以上所有的数据都在\([-1000,1000]\)内。
输出格式:
一行,一个整数,长方形盒子剩余的最小空间(结果四舍五入输出)
爆搜一下即可,这个幽默的数据。
然而,它居然问的是最小空间!!!!
我输出了最大面积。。。。
而且样例给的最小空间居然等于最大面积,绝对故意的。。。
code:
#include <cstdio>
#include <cmath>
const int N=7;
const double pi=3.1415926;
int up,ri,le,dow,x[N],y[N],n;
double fmax(double a,double b) {return a>b?a:b;}
double fmin(double a,double b) {return a<b?a:b;}
int min(int a,int b) {return a<b?a:b;}
int abs(int a) {return a>0?a:-a;}
int used[N];
double yuan[N],ans=0,dis[N][N];//圆的半径
double get(int a,int b)
{
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
void init()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=get(i,j);
}
double get(int id)
{
double rm=1e300;
rm=min(min(x[id],ri-x[id]),min(y[id],up-y[id]));
for(int i=1;i<=n;i++)
if(yuan[i]!=0)
rm=fmin(dis[id][i]-yuan[i],rm);
return fmax(0.0,rm);
}
void dfs(int dep)
{
if(dep==n+1)
{
double sum=0;
for(int i=1;i<=n;i++)
sum+=yuan[i]*yuan[i]*pi;
ans=fmax(sum,ans);
return;
}
for(int i=1;i<=n;i++)
if(!used[i])
{
used[i]=1;
yuan[i]=get(i);
dfs(dep+1);
yuan[i]=0.0;
used[i]=0;
}
}
int main()
{
int x1,y1,x2,y2;
scanf("%d",&n);
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
up=abs(y1-y2),ri=abs(x1-x2);
le=min(x1,x2),dow=min(y1,y2);
for(int i=1;i<=n;i++)
{
scanf("%d%d",x+i,y+i);
x[i]-=le,y[i]-=dow;
}
init();
dfs(1);
ans=double(up*ri)-ans;
int an=int(ans+0.5);
printf("%d\n",an);
return 0;
}
2018.5.20
最新文章
- Solr嵌套子文档的弊端以及一种替代方式
- 更新日志 - BugHD 新增邮件告警功能
- BZOJ4107 : [Wf2015]Asteroids
- 通过 ec2-api / boto 调用 OpenStack 功能
- configure: error: C++ compiler cannot create executables
- vc6
- (总结)Web性能压力测试工具之WebBench详解
- Win7中隐藏的上帝模式——GodMode
- hdu 4008 树形dp
- wpf 绑定失效的原因及解决方案
- HDU 4998 Rotate
- Linux - SVN下载项目
- C#采用OpenXml给word里面插入图片
- JavaScript数据结构与算法(一) 栈的实现
- Mysql参数汇总
- C#操作DataTable类
- 搭建vscode+vue环境
- CF 633 E. Binary Table
- 51Nod 1459:迷宫游戏(最短路)
- js中获取当前url参数值的一个方法