Problem 1133 : Water Tank

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1133&lang=jp
Problem 1133 : Water Tank

AOJの問題です。

• 問題概要

水槽の大きさは決まっていて、その中にある仕切りの高さと位置が入力として与えられる。
さらに、蛇口の位置とそこから毎秒でる水の量が与えられる。

指定された時間と位置の水位を出力せよ。

• 解法

仕切られたひとつづつを、容量をもった箱とみなす。
そして、求めたい時間までにでる水をいったんすべていれてしまう。
容量を超えていたらとなりの箱（壁の低い方）に溢れた分をいれる。
溢れようとした先がマンタンの場合は二つの箱を連結し、ひとつの箱とみなす。

• ソース

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>

using namespace std;

class Tank{
public:
  int x, w, h1, h2, f, now;
  bool ad;
  int capa(){
    return w * min(h1, h2) *30;
  }
  int next(){
    if(h1 > h2){
      return 1;
    }
    else return -1;
  }

  int r(){
    return x + w;
  }
  bool operator < (const Tank t)const{
    return x < t.x;
  }
  double height(){
    return min((double)50, (double)now/(double)(w*30));
  } 
  Tank(){
    x = w = h1 = h2 = f = now = 0;
    ad = false;
  }
  void fill(int t){
    if(!ad)return;
    now += t*f;
  }
  bool full(){
    return now > capa();
  }
};

main(){

  int dataset;

  cin >> dataset;

  for(int data=0; data<dataset; data++){
    int n;
    cin >> n;

    vector<Tank> t(n+1);
    int prex = 0, preh=50;
    for(int i=0; i<n; i++){
      t[i].x = prex;
      int tmp;
      cin >> tmp;
      t[i].w = tmp - prex;
      prex = tmp;
      cin >> t[i].h2;
      t[i].h1 = preh;
      preh = t[i].h2;
    }
    t[n].x = prex;
    t[n].w = 100 - prex;
    t[n].h1 = preh;
    t[n].h2 = 50;
    
    cin >> n;
    int now=0;
    for(int i=0; i<n; i++){
      int tmp;
      cin >> tmp;
      while( t[now].r() < tmp){
	now++;
      }
      t[now].ad = true;
      cin >> tmp;
      t[now].f += tmp;
    }

    cin >> n;

    for(int j=0; j<n; j++){
      vector<Tank> v=t;

      int x, time;
      cin >> x >> time;

      for(int i=0; i<v.size(); i++){
	v[i].fill(time);
      }
      while(1){
	bool flg = false;
	for(int i=0; i<v.size(); i++){
	  if(v[i].full()){
	    flg = true;
	    int next = v[i].next() + i;
	    if(v[next].capa() == v[next].now && v[next].next() + next == i){
	      Tank merge;
	      if(v[i].next() == -1){
		merge.h1 = v[next].h1;
		merge.h2 = v[i].h2;
		merge.x = v[next].x;
	      }
	      else{
		merge.h1 = v[i].h1;
		merge.h2 = v[next].h2;
		merge.x = v[i].x;
	      }
	      merge.w = v[i].w + v[next].w;
	      merge.ad = (v[i].ad || v[next].ad);
	      merge.f  = v[i].f + v[next].f;
	      merge.now = v[i].now + v[next].now;
	      v.erase(v.begin() + min(next, i));
	      v.erase(v.begin() + min(next, i));
	      v.push_back(merge);
	      sort(v.begin(), v.end());
	      break;
	    }
	    else {
	      v[next].now += (v[i].now - v[i].capa());
	      v[i].now = v[i].capa();
	      break;
	    }
	  }
	}
	if(!flg){
	  break;
	}
	if(v.size() == 1){
	  break;
	}
      }

      for(int i=0; i<v.size(); i++){
	if(v[i].x< x  && x < v[i].r()){
	  printf("%.5lf\n",v[i].height());
	  break;
	}
      }
    }
  }
}