/**//* 一个矩形,分成几块小矩形,每个小矩形有深度 其中某个矩形会有水不断流入,问填满所有矩形所需的时间 一个矩形填满后会外溢,每条边的速度跟边长成比例
我一开始不敢写,没想到很清晰的思路 watashi的blog写用dijkstra 发现确实很像Orz 然后照着dij写,感觉挺清晰的 注意可能几个同时慢,还有更新总长时要减去2被公共边 */ #include<cstdio> #include<cstring> #include<algorithm> #include<vector>
using namespace std;
const double EPS = 1e-4;
inline double sign(double x) { return x < -EPS ? -1 : x > EPS; }
struct Pool { double x1,y1,x2,y2,d,len; void read() { scanf("%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&d); if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); d = d/100*(x2-x1)*(y2-y1); len = 2*(x2-x1)+2*(y2-y1); } double touch(Pool & B) { if(x2 == B.x1 || x1 == B.x2) { return min(y2,B.y2) - max(y1,B.y1); } if(y2 == B.y1 || y1 == B.y2) { return min(x2,B.x2) - max(x1,B.x1); } return 0;/**/////////注意返回0呀!!! } void print() { printf("pool %.2f %.2f %.2f %.2f\n",x1,y1,x2,y2,d); } };
Pool pool[110]; double t[110],pre[110]; bool vi[110]; vector<pair<int,double> > E[110];
int main() {
#ifdef ONLINE_JUDGE #else freopen("in","r",stdin); #endif
int n , p; double x, y,s; while( ~scanf("%d%lf%lf%d%lf",&n,&x,&y,&p,&s)) { for(int i = 0 ; i < n ; i++) { E[i].clear(); } p--; s /= 1000; for(int i = 0 ; i < n; i++) { pool[i].read(); for(int j = 0 ; j < i ;j++) { double touch = pool[i].touch(pool[j]); if(sign(touch) > 0) { E[i].push_back(make_pair(j,touch)); E[j].push_back(make_pair(i,touch)); } } t[i] = 1e30; vi[i] = false; pre[i] = 0.0; } t[p] = pool[p].d / s;
double ans = 0 , length = 0;
for(int i = 0 ; i < n; i++) { vector<int> VT;//找到最早满的 for(int j = 0 ; j < n; j++) if(!vi[j]) { if(VT.size() == 0 || sign(t[VT[0]] - t[j]) == 0 )VT.push_back(j); else if(sign(t[VT[0]]-t[j])>0) { VT.clear(); VT.push_back(j); } }
if(VT.size() == 0)break;
double needTime = t[VT[0]]; if(sign(length)) { for(int j = 0 ; j < n ;j++)//对所有未满的pool上升一定高度 { if(vi[j])continue; pool[j].d -= pre[j]/length*s*needTime; } }
ans += needTime; //updata length for(int ii = 0 ; ii < VT.size() ; ii++)//对于同时满的,认为排在前面的先满 { int ID = VT[ii]; length += pool[ID].len; for(int jj = 0 ; jj < E[ID].size() ; jj++) { if(vi[E[ID][jj].first])length -= 2*E[ID][jj].second; } vi[ID] = true; }
//update vi[] = false 重新计算时间和流入水的边长 for(int j = 0 ; j < n; j++) { if(vi[j])continue; double speed = 0; for(int ii = 0 ; ii < E[j].size() ; ii++) { if(vi[E[j][ii].first]) { speed += E[j][ii].second; } } pre[j] = speed; speed *= s / length; t[j] = pool[j].d / speed; } } printf("%.4f\n",ans); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|