C++

「搜索 & 精度」Luogu 1378 油滴拓展

前言

写这篇博客,我真的很荣幸!看了看时间,现在是2017年11月7日 BJS 22:32,为什么这么说呢,我从今天下午19:40时和机房小伙伴们语音聊天,准备做一下传说中的萌新到大佬的巨大门槛(伪)——油滴拓展,传说中的调试9 hours也不是闹着玩的。有幸的是,这道题思路上没什么门槛,就是全排列,然而需要在精度上格外注意。其实double就可以了,还有很多流传的π=3.14就会WA(果然WA 30)让我感觉超级害怕。但是所幸的是,我AC掉了这道题了!历时3个小时。

看题:

题目描述

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

注:圆的面积公式V=pirr,其中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

输入样例2:

3 
-98 5 30 30 
-42 11 
-51 17 
-11 22

输出样例2:

2547

题解

再一次表示很荣幸能AC这道神级的题目,那么我来说说题解吧:我一次提交AC 60,当精度什么的都计算的没有问题的时候,就会有一个另外的问题,也就是:我现在想放的油滴是否在别的已经扩散的油滴的内部,如果是,那么我现在放不了这个油滴了。

所以也就是说,我需要在判断距离的时候就判断一下是不是会gg,于是就有了以下代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define pi acos(-1)

int pai[10];
int n,a,b,c,e;
double dis[10][10],m=0.0,ans=0.0,t;
bool vis[10],f,gg;
struct dot{double x,y,m,r;}d[10];

double min_(double a,double b){return a+0.0000001>b+0.0000001 ? b : a;}

void work(){
    double ss=0.0;
    for(int i=1;i<=n;i++){
        m=9999999.9999;gg=0;//gg表示放这个油滴会不会gg
        for(int j=1;j<i;j++){
            if(dis[pai[i]][pai[j]]-d[pai[j]].r<m && dis[pai[i]][pai[j]]-d[pai[j]].r>0.000001) m=dis[pai[i]][pai[j]]-d[pai[j]].r;
            if(dis[pai[i]][pai[j]]-d[pai[j]].r<0.000001) gg=1;
        }
        if(!gg) d[pai[i]].r=min_(d[pai[i]].m,m);
        if(!gg) ss+=(d[pai[i]].r*d[pai[i]].r*pi);
    }
    if(ss>ans) ans=ss;
}

void qp(int l){//生成全排列
    if(l==n+1){work();return ;}
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            pai[l]=i;
            qp(l+1);
            vis[i]=0;
        }
    }
}

int main(){    
    cin>>n;
    cin>>a>>b>>c>>e;
    int size=(abs(a-c)*abs(b-e));
    for(int i=1;i<=n;i++) cin>>d[i].x>>d[i].y;
    //预处理两点之间距离
      for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=sqrt((d[i].x-d[j].x)*(d[i].x-d[j].x)+(d[i].y-d[j].y)*(d[i].y-d[j].y));
    for(int i=1;i<=n;i++){
        m=9999999.9;
        if(fabs(d[i].x-a)<m) {m=fabs(d[i].x-a);d[i].m=m;}
        if(fabs(d[i].x-c)<m) {m=fabs(d[i].x-c);d[i].m=m;}
        if(fabs(d[i].y-b)<m) {m=fabs(d[i].y-b);d[i].m=m;}
        if(fabs(d[i].y-e)<m) {m=fabs(d[i].y-e);d[i].m=m;}
    }
      //边生成全排列的过程中计算面积
    qp(1);
    cout<<size<<" "<<ans<<endl;
    cout<<(int)(size-ans+0.5)<<endl;
    return 0;
}

同时也很感谢机房的各位:zhy yhs 大佬陪我度过这神殿级的一题,感谢zhy帮我远程调试bug。(虽说你们回寝室了我才AC)也许,这会成为我OI生涯比较骄傲的事情吧。

分享到