【洛谷P1378】油滴扩展

搜索……

PS一个坑点:r<=0时并不是舍弃这种情况,而是让r=0

(因为每个点都要放一滴油)(读题啊!)

 #include<cstdio>
#include<cstring>
#include<cmath>
#define dd double
using namespace std;
const int N=;
const dd pai=3.1415926535,INF=;
int flag[N],n;
dd xx,yy,x2,y2,x[N],y[N];
//'int y1' redeclared as different kind of symbol,保留字
dd dx[N][],dy[N][],dis[N][N],r[N],ans;
void swap(dd &a,dd &b){
dd tmp=a;
a=b;
b=tmp;
}
dd min(dd a,dd b){
return a<b?a:b;
}
dd max(dd a,dd b){
return a>b?a:b;
}
void dfs(int step,dd size){
if (step==n){
ans=max(ans,size);
return;
}
for (int i=;i<=n;i++){
if (!flag[i]){
dd len=min(dx[i][],dx[i][]);
len=min(len,min(dy[i][],dy[i][]));
for (int j=;j<=n;j++)
if (flag[j]){
dd l=dis[i][j]-r[j];
if (l>)
len=min(len,l);
else
len=;//***
}
flag[i]=;
r[i]=len;
size+=pai*r[i]*r[i];
dfs(step+,size);
flag[i]=;
size-=pai*r[i]*r[i];
}
}
}
int main(){
scanf("%d",&n);
scanf("%lf %lf %lf %lf",&xx,&yy,&x2,&y2);
for (int i=;i<=n;i++)
scanf("%lf %lf",&x[i],&y[i]);
if (xx>x2)
swap(xx,x2);
if (yy>y2)
swap(yy,y2);
for (int i=;i<=n;i++){
dx[i][]=x2-x[i];
dx[i][]=x[i]-xx;
dy[i][]=y2-y[i];
dy[i][]=y[i]-yy;
for (int j=;j<=n;j++){
int cx=x[i]-x[j];
int cy=y[i]-y[j];
dis[i][j]=sqrt(cx*cx+cy*cy);
}
}
ans=;
dfs(,);
dd s=(x2-xx)*(y2-yy)-ans;
int S=s+0.5;
printf("%d",S);
return ;
}

STD

上一篇:物联网安全Wi-Fi漫游


下一篇:VMWare linux安装mysql 5.7.13