#include #include #include #include #include #include #include #include #include using namespace std; typedef pair DPair; struct Cell { Cell() {} Cell(double lp, double lh, double rp, double rh, double w) { leftpos = lp; leftheight = lh; rightpos = rp; rightheight = rh; water = w; } double leftpos; double leftheight; double rightpos; double rightheight; double water; double MaxWater() const { return (rightpos - leftpos) * min(leftheight, rightheight) * 30.0; } double WaterHeight() const { return water / 30.0 / (rightpos - leftpos); } void print() const { cout << leftpos << ", " << leftheight << ", " << rightpos << ", " << rightheight << ", " << water << endl; } }; void print(vector& tank) { cout << "---" << endl; for (int i = 0; i < tank.size(); ++i) { tank[i].print(); } } bool flow(vector& tank) { bool changed = false; if (tank.size() <= 1) { return false; } for (int i = 0; i < tank.size(); ++i) { if (tank[i].water <= tank[i].MaxWater()) { continue; } double flowed = tank[i].water - tank[i].MaxWater(); tank[i].water = tank[i].MaxWater(); changed = true; if (tank[i].leftheight < tank[i].rightheight) { tank[i - 1].water += flowed; } else { tank[i + 1].water += flowed; } } return changed; } bool merge(vector& tank) { vector tmptank; bool changed = false; bool tmp = false; do { tmptank.clear(); tmp = false; int i; for (i = 0; i < tank.size() - 1; ++i) { if (tank[i].water >= tank[i].MaxWater() && tank[i + 1].water >= tank[i + 1].MaxWater() && tank[i].leftheight > tank[i].rightheight && tank[i + 1].leftheight < tank[i + 1].rightheight) { Cell cell(tank[i].leftpos, tank[i].leftheight, tank[i + 1].rightpos, tank[i + 1].rightheight, tank[i].water + tank[i + 1].water); tmptank.push_back(cell); changed = true; tmp = true; ++i; } else { tmptank.push_back(tank[i]); } } if (i < tank.size()) { tmptank.push_back(tank[tank.size() - 1]); } swap(tank, tmptank); } while (tmp); return changed; } bool operator<(const pair& lhs, const pair& rhs) { return lhs.first.second < rhs.first.second; } void solve(vector& tank, vector& jag, vector& measure) { // print(tank); vector > measure2; for (int i = 0; i < measure.size(); ++i) { measure2.push_back(make_pair(measure[i], i)); } sort(measure2.begin(), measure2.end()); vector answer; double time = 0.0; for (int i = 0; i < measure2.size(); ++i) { bool changed = false; // mizu wo ireru for (int j = 0; j < jag.size(); ++j) { for (int k = 0; k < tank.size(); ++k) { if (tank[k].leftpos < jag[j].first && jag[j].first < tank[k].rightpos) { tank[k].water += jag[j].second * (measure2[i].first.second - time); break; } } } do { // print(tank); bool b1 = flow(tank); // print(tank); bool b2 = merge(tank); changed = b1 || b2; } while (changed); for (int j = 0; j < tank.size(); ++j) { if (tank[j].leftpos <= measure2[i].first.first && measure2[i].first.first <= tank[j].rightpos) { double height = tank[j].WaterHeight(); if (height >= 50.0) { height = 50.0; } answer.push_back(height); break; } } time = measure2[i].first.second; } for (int i = 0; i < measure.size(); ++i) { for (int k = 0; k < answer.size(); ++k) { if(measure2[k].second != i) continue; static char buffer[32]; // sprintf(buffer, "%5lf", answer[k]); //cout << buffer << endl; cout << answer[k] << endl; } } } int main() { int D; cin >> D; while (D--) { int N, M, L; vector tank; cin >> N; double lp = 0.0; double lh = 50.0; double rp; double rh; for (int i = 0; i < N; ++i) { cin >> rp >> rh; tank.push_back(Cell(lp, lh, rp, rh, 0.0)); lp = rp; lh = rh; } tank.push_back(Cell(lp, lh, 100.0, 50.0, 0.0)); vector jag; cin >> M; for (int i = 0; i < M; ++i) { double f, a; cin >> f >> a; jag.push_back(DPair(f, a)); } vector measure; cin >> L; for (int i = 0; i < L; ++i) { double p, t; cin >> p >> t; measure.push_back(DPair(p, t)); } solve(tank, jag, measure); } }