P1378 油滴扩展——搜索小记

P1378 油滴扩展

记得这道题好久以前（好像是上个学期？） 就想做了，但是看着里面的半径边界好像很难处理就没做（主要是当时刚学OI(菜还给自己找借口)）；

今天上午一直研究SG函数，做的都自闭了，晚上想刷刷水题缓解一下心情，就又看到了这道题；

一看数据范围，原来挺简单的，还是个绿题，听着音乐开始切；

有几个坑点吧，第一他给的长方形坐标点不是左下角和右上角；

第二，求距离要开根号（也就我会忘了……）；

判断时记录一下前面的圆半径就好了。

全排列。

还有

引用cmath库，开变量的时候不要用y1!!!!!!!!!

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef double dd;

const dd p=3.1415926535;

struct node

{

    dd x,y;

}a[];

int n;

dd x1,y3,x2,y2;

int vis[],b[];

dd ans=1e9;

dd s;

dd r[];

dd get_dis(int x,int y)

{

    return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));

}

dd check(int x)

{

    dd r_ma=1e9;

    dd dis=;

    for(int i=;i<x;i++)

    {

        dis=get_dis(b[i],b[x]);

        if(dis<=r[b[i]]) return ;

        r_ma=min(r_ma,dis-r[b[i]]);

    }

    r_ma=min(r_ma,(a[b[x]].y-y3));

    r_ma=min(r_ma,(a[b[x]].x-x1));

    r_ma=min(r_ma,(y2-a[b[x]].y));

    r_ma=min(r_ma,(x2-a[b[x]].x));

    r[b[x]]=r_ma;

    return p*r_ma*r_ma;

}

void dfs(int x)

 {

     if(x==n+)

     {

         dd sum=;

         for(int i=;i<=n;i++)

         {

             sum+=check(i);

         }

         //printf("%lf\n",sum);

         ans=min(ans,(s-sum));

         return ;

     }

     for(int i=;i<=n;i++)

     {

         if(!vis[i])

         {

             vis[i]=;

             b[x]=i;

             dfs(x+);

             vis[i]=;

         }

     }

 }

 dd qw;

int main()

{

    scanf("%d",&n);

    scanf("%lf%lf%lf%lf",&x1,&y3,&x2,&y2);

    if(x2<x1)

    {

        if(y3>y2)

        {

            qw=x2;x2=x1;x1=qw;

            qw=y2;y2=y3;y3=qw;

        }

        else if(y3<y2)

        {

            dd xi=x2,yi=y3;

            dd xj=x1,yj=y2;

            x1=xi;y3=yi;x2=xj;y2=yj;

        }

    }

    else if(y3>y2)

    {

        qw=y3;

        y3=y2;

        y2=qw;

    }

    s=(x2-x1)*(y2-y3);

    for(int i=;i<=n;i++)

    {

        scanf("%lf%lf",&a[i].x,&a[i].y);

    }

    dfs();

    printf("%.0lf",ans);

    return ;

}