油滴扩展

窝又开始做洛谷的题了

先说现在写的：

• 1.四舍五入有专门的函数\(round\)，返回的还是浮点型。（不加也\(A\)了）
• 2.\(tmp[j]\)写成\(j\)，大意了。

之前的写法：

• 1.太复杂
• 2.中间有转成\(int\)，可能被卡了精度
• 3.记录的是半径的平方，好像还算错了，懒得改了

\(AC:\)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double pi = 3.1415926;
int n,x1,x2,yt,y2,tmp[12];
struct node{
    int x,y;
}a[10];
bool book[12];
double ans=1000000000.0,r[12];
double min(double xt,double yt)
{
    if(xt<yt) return xt;
    return yt;
}
int mint(int a,int b)
{ if(a<b) return a; return b; }
void work(int t)
{
    int res=1e9;
    res=mint(res,mint(abs(x1-a[tmp[t]].x),abs(x2-a[tmp[t]].x)));
    res=mint(res,mint(abs(yt-a[tmp[t]].y),abs(y2-a[tmp[t]].y)));
    r[tmp[t]]=min(r[tmp[t]],(double)res);
}
double dis(int a,int b,int c,int d)
{
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
void print()
{
    for(int i=1;i<=n;i++)
     r[i]=1000000000.0;
    work(1);
    for(int i=2;i<=n;i++)
    {
        int t=tmp[i];
        work(i);
        for(int j=1;j<i;j++)
         r[t]=min(r[t],max(dis(a[t].x,a[t].y,a[tmp[j]].x,a[tmp[j]].y)-r[tmp[j]],0.0));
    }
    double ansp=(double)(abs(y2-yt)*abs(x2-x1));
    for(int i=1;i<=n;i++)
     ansp-=pi*r[i]*r[i];
    ans=min(ans,ansp);
    return ;
}
void dfs(int t)
{
    if(t>n) { print(); return ;}
    for(int i=1;i<=n;i++)
    if(!book[i])
    {
        book[i]=1; tmp[t]=i;
        dfs(t+1);
        book[i]=0;
    }
}
int main()
{
    scanf("%d",&n);
    scanf("%d%d%d%d",&x1,&yt,&x2,&y2);
    for(int i=1;i<=n;i++)
     scanf("%d%d",&a[i].x,&a[i].y);
    dfs(1);
    ans=round(ans);
    printf("%.0lf\n",ans);
    return 0;
}

油滴扩展

原文：https://www.cnblogs.com/karryW/p/11552234.html