| 
		
			| 
	
	
		
			  /**//* 
  一个矩形,分成几块小矩形,每个小矩形有深度 
  其中某个矩形会有水不断流入,问填满所有矩形所需的时间 
  一个矩形填满后会外溢,每条边的速度跟边长成比例 
  
  我一开始不敢写,没想到很清晰的思路 
  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搜索最新评论
	
 |  |