 /**//*
一个矩形,分成几块小矩形,每个小矩形有深度
其中某个矩形会有水不断流入,问填满所有矩形所需的时间
一个矩形填满后会外溢,每条边的速度跟边长成比例

我一开始不敢写,没想到很清晰的思路
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
搜索
最新评论

|
|