M_sea

洛谷1378 油滴扩展
Luogu分析完了,我氵搜索都不会打了数据范围极小,可以套用这张沙雕图。枚举每一步在哪放油。注意如果这个位置已经被...
扫描右侧二维码阅读全文
25
2018/11

洛谷1378 油滴扩展

Luogu

分析

完了,我氵搜索都不会打了

233

数据范围极小,可以套用这张沙雕图。

枚举每一步在哪放油。注意如果这个位置已经被覆盖了就不能放了。

然后确定半径见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=6+10;
const double PI=acos(-1.0);

int n;
int U,D,L,R;
int x[MAXN],y[MAXN];
int vis[MAXN];
double r[MAXN];
double ans=1e9;

inline double dis(int a,int b) {
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}

inline void Dfs(int sum,double S) {
    if (sum==n+1) {
        ans=min(ans,S);
        return;
    }
    for (re int i=1;i<=n;++i) {
        if (vis[i]) continue;
        int flag=0;
        for (re int j=1;j<=n;++j) {
            if (vis[j]&&r[j]-dis(i,j)>1e-6) {
                flag=1;
                break;
            }
        }
        if (flag) {
            vis[i]=1; Dfs(sum+1,S); vis[i]=0;
            continue;
        }
        r[i]=min(min(U-y[i],y[i]-D),min(R-x[i],x[i]-L));
        for (re int j=1;j<=n;++j)
            if (vis[j]&&r[i]+r[j]-dis(i,j)>1e-6) r[i]=dis(i,j)-r[j];
        vis[i]=1; Dfs(sum+1,S-PI*r[i]*r[i]); vis[i]=0;
    }
}

int main() {
    n=read();
    L=read(),U=read(),R=read(),D=read();
    if (U<D) swap(U,D); if (R<L) swap(L,R);
    for (re int i=1;i<=n;++i) x[i]=read(),y[i]=read();
    Dfs(1,(R-L)*(U-D));
    printf("%d\n",(int)round(ans));
    return 0;
}
最后修改:2018 年 12 月 02 日 09 : 19 PM

发表评论