 /**//*
一個(gè)矩形,分成幾塊小矩形,每個(gè)小矩形有深度
其中某個(gè)矩形會(huì)有水不斷流入,問(wèn)填滿所有矩形所需的時(shí)間
一個(gè)矩形填滿后會(huì)外溢,每條邊的速度跟邊長(zhǎng)成比例

我一開(kāi)始不敢寫,沒(méi)想到很清晰的思路
watashi的blog寫用dijkstra
發(fā)現(xiàn)確實(shí)很像Orz
然后照著dij寫,感覺(jué)挺清晰的
注意可能幾個(gè)同時(shí)慢,還有更新總長(zhǎng)時(shí)要減去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呀?。。?/span>
}
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++)//對(duì)所有未滿的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++)//對(duì)于同時(shí)滿的,認(rèn)為排在前面的先滿
 {
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 重新計(jì)算時(shí)間和流入水的邊長(zhǎng)
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
搜索
最新評(píng)論

|
|