栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3372 Gone Swimming

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3372 Gone Swimming

#include<cstring>#include<cstdio>#include<algorithm>using namespace std;const int maxn =110;const double inf = 1e30;const double eps =1e-8;int dcmp(double x){ if(x<-eps) return -1; return x>eps;}double v[maxn];int x,y,n;double s;int x1[maxn],h[maxn],y1[maxn],x2[maxn],y2[maxn];int g[maxn][maxn],first,mk[maxn];double size[maxn];int main(){ while(scanf("%d %d %d %d %lf",&n,&x,&y,&first,&s)!=EOF){ memset(g,0,sizeof(g)); memset(v,0,sizeof(v)); memset(mk,0,sizeof(mk)); for(int i=1;i<=n;i++){ scanf("%d %d %d %d %d",&x1[i],&y1[i],&x2[i],&y2[i],&h[i]); size[i]=(x2[i]-x1[i])*(y2[i]-y1[i])*h[i]*10; for(int j=x1[i];j<x2[i];j++){ for(int k=y1[i];k<y2[i];k++) g[j][k]=i; } } v[first]=s; double ans=0; for(int i=1;i<=n;i++){ int k=-1; double tmpt=inf; for(int j=1;j<=n;j++){ if(mk[j]==0&&dcmp(v[j])&&dcmp(size[j]/v[j]-tmpt)<0){ tmpt=size[j]/v[j]; k=j; } }  ans+=tmpt; mk[k]=1; for(int j=x1[k];j<x2[k];j++){ for(int t=y1[k];t<y2[k];t++){ g[j][t]=0; } } for(int j=1;j<=n;j++) if(mk[j]==0) size[j]-=v[j]*tmpt; int cnt=0; memset(v,0,sizeof(v)); for(int j=1;j<x;j++){ for(int k=0;k<y;k++){ if(g[j-1][k]==0&&g[j][k]) v[g[j][k]]=v[g[j][k]]+1,cnt++; else if(g[j-1][k]&&g[j][k]==0) v[g[j-1][k]]=v[g[j-1][k]]+1,cnt++; } } for(int j=0;j<x;j++){ for(int k=1;k<y;k++){ if(g[j][k-1]==0&&g[j][k]) v[g[j][k]]++,cnt++; else if(g[j][k]==0&&g[j][k-1]) v[g[j][k-1]]++,cnt++; } } for(int j=0;j<y;j++){ if(0==g[0][j]) cnt++; if(0==g[x-1][j]) cnt++; } for(int j=0;j<x;j++){ if(0==g[j][0]) cnt++; if(0==g[j][y-1]) cnt++; } for(int j=1;j<=n;j++) v[j]=v[j]*s/cnt; } printf("%.6lfn",ans); } return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/372326.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号