#include #include #include using namespace std; #define AQUARIUM_DEPTH 30 #define AQUARIUM_HEIGHT 50 #define AQUARIUM_WIDTH 100 #define NDIVIDER_MAX 10 #define NFAUCET_MAX 10 #define AQUARIUM_VOLUME (AQUARIUM_DEPTH*AQUARIUM_HEIGHT*AQUARIUM_WIDTH) class Partition { public: Partition() {} Partition( int leftHeight, int rightHeight, int length, Partition *left, Partition *right ) : leftHeight(leftHeight), rightHeight(rightHeight), length(length), leftPartition(left), rightPartition(right), waterAmount(0) { lowerHeight = min(leftHeight, rightHeight); lowerVolume = lowerHeight * length * AQUARIUM_DEPTH; } void pushWater( int amount ) { waterAmount += amount; // 溢れが生じていない場合. if ( waterAmount <= lowerVolume ) return; // 溢れが生じたので隣接する区画にオーバーフロー. if ( lowerHeight == leftHeight ) leftOverflow(); else rightOverflow(); } Partition *getNext() { return rightPartition; } int getWidth() { return length; } double getWaterLevel() { return (double)waterAmount / (length * AQUARIUM_DEPTH); } private: int leftHeight, rightHeight; int lowerHeight, lowerVolume; int length; Partition *leftPartition, *rightPartition; int waterAmount; void leftOverflow() { const int excess = waterAmount - lowerVolume; waterAmount = lowerVolume; Partition &L = *leftPartition; Partition &R = *rightPartition; // 隣接する区画も満たされている場合はマージする. でなければプッシュ. // 満たされているとは, 仕切を取り除いても何の問題もないということである. if ( L.waterAmount != L.lowerVolume || L.lowerHeight != lowerHeight ) L.pushWater(excess); else mergeLeft(L, R, excess); } void mergeLeft( Partition &L, Partition &R, int excess ) { L.rightHeight = rightHeight; L.lowerHeight = min(L.leftHeight, L.rightHeight); L.length = L.length + length; L.lowerVolume = L.length * L.lowerHeight * AQUARIUM_DEPTH; L.waterAmount = L.waterAmount + waterAmount; L.rightPartition = rightPartition; R.leftPartition = leftPartition; L.pushWater(excess); } void rightOverflow() { const int excess = waterAmount - lowerVolume; waterAmount = lowerVolume; Partition &R = *rightPartition; Partition &L = *leftPartition; if ( R.waterAmount != R.lowerVolume || R.lowerHeight != lowerHeight ) R.pushWater(excess); else mergeRight(R, L, excess); } void mergeRight( Partition &R, Partition &L, int excess ) { R.leftHeight = leftHeight; R.lowerHeight = min(R.leftHeight, R.rightHeight); R.length = R.length + length; R.lowerVolume = R.length * R.lowerHeight * AQUARIUM_DEPTH; R.waterAmount = R.waterAmount + waterAmount; R.leftPartition = leftPartition; L.rightPartition = rightPartition; R.pushWater(excess); } }; class Divider { public: int position, height; }; class Faucet { public: int position, amount; }; int ndivider, nfaucet; Partition P[AQUARIUM_WIDTH+2]; Divider D[NDIVIDER_MAX]; Faucet F[NFAUCET_MAX]; double compute( int position, int currTime ) { int npartition = 1; int prevHeight = AQUARIUM_HEIGHT; int prevPosition = 0; for ( int n = 0; n < ndivider; n++, npartition++ ) P[npartition] = Partition(prevHeight, D[n].height, D[n].position - prevPosition, &P[npartition-1], &P[npartition+1]), prevHeight = D[n].height, prevPosition = D[n].position; // P[0] はリストヘッダとして確保. P[0] = Partition(0, 0, 0, NULL, &P[1]); P[npartition] = Partition(prevHeight, AQUARIUM_HEIGHT, AQUARIUM_WIDTH - prevPosition, &P[npartition-1], &P[npartition+1]); npartition++; // 終端は P[npartition]. P[npartition] = Partition(0, 0, 0, &P[npartition-1], NULL); // 同時にすべての蛇口を開けて T 秒経過させ, 閉じることと, // 一つの蛇口を開けて T 秒まち, 閉じる, 次の蛇口を開けて T 秒待ち, という動作を繰り返すことの // 結果は同じでありそう, ということに依存する. for ( int n = 0; n < nfaucet; n++ ) { const int faucetPosition = F[n].position; const int amount = F[n].amount * currTime; Partition *curr = P[0].getNext(); int partitionPosition = 0; while ( curr != &P[npartition] && partitionPosition + curr->getWidth() < faucetPosition ) partitionPosition += curr->getWidth(), curr = curr->getNext(); curr->pushWater(amount); } Partition *curr = P[0].getNext(); int partitionPosition = 0; while ( curr != &P[npartition] && partitionPosition + curr->getWidth() < position ) partitionPosition += curr->getWidth(), curr = curr->getNext(); return curr->getWaterLevel(); } int main() { int ntest; cin >> ntest; for ( int nt = 0; nt < ntest; nt++ ) { cin >> ndivider; for ( int i = 0; i < ndivider; i++ ) cin >> D[i].position >> D[i].height; cin >> nfaucet; for ( int i = 0; i < nfaucet; i++ ) cin >> F[i].position >> F[i].amount; int faucetAmountSum = 0; for ( int i = 0; i < nfaucet; i++ ) faucetAmountSum += F[i].amount; int nquery; cin >> nquery; for ( int n = 0; n < nquery; n++ ) { int position, currTime; cin >> position >> currTime; // 水槽をいっぱいにするのに充分な時間が経過している場合は // シミュレーションしてはいけない. 側面からの溢れに対応していないため. if ( faucetAmountSum * currTime >= AQUARIUM_VOLUME ) printf("%.4lf\n", (double)AQUARIUM_HEIGHT); else printf("%.4lf\n", compute(position, currTime)); } } return 0; }