#include #include #include #include using namespace std; class tree{ public: tree(int st,int ed,int depth,tree *l,tree *r){ this->st=st; this->ed=ed; this->depth=depth; this->l=l; this->r=r; p=NULL; water=0; } ~tree(){ if (l) delete l; if (r) delete r; } // debug... void print(int d=0){ for (int i=0;iprint(d+1); if (r) r->print(d+1); } void dry(){ water=0; if (l) l->dry(); if (r) r->dry(); } tree *find(int x){ if (l==NULL&&r==NULL) return this; else if (xed) return l->find(x); else return r->find(x); } void pour_at(int x,int v){ find(x)->pour(v,0); } double height_at(int x){ return find(x)->height(); } double height(){ double d=((double)water)/(ed-st)/30; if (p) d+=p->height(); return d; } bool full(){ return water>=(ed-st)*depth*30; } void pour(int v,int dir){ if (l&&r&&(!l->full()||!r->full())){ if (!l->full()&&!r->full()) (dir==0?l:r)->pour(v,dir); else if (!l->full()) l->pour(v,1); else if (!r->full()) r->pour(v,0); } else{ int full=(ed-st)*depth*30; if (water+v>full){ int remain=v-(full-water); water=full; if (p) p->pour(remain,0); } else water+=v; } } int st,ed; int depth; int water; tree *l,*r,*p; }; tree *gen_tree(int *part,int start,int end,int depth) { int maxv=0,maxi=0; for (int i=start+1;imaxv){ maxv=part[i]; maxi=i; } } if (maxv==0) return new tree(start,end,depth,NULL,NULL); else{ tree *l=gen_tree(part,start,maxi,maxv); tree *r=gen_tree(part,maxi,end,maxv); tree *ret=new tree(start,end,depth-maxv,l,r); return (l->p=r->p=ret); } } int main() { int d;cin>>d; while(d--){ int part[101]={0}; int n;cin>>n; while(n--){ int b,h;cin>>b>>h; part[b]=h; } tree *tr=gen_tree(part,0,100,50); //tr->print(); int m;cin>>m; vector > taps; while(m--){ int f,a;cin>>f>>a; taps.push_back(make_pair(f,a)); } int l;cin>>l; while(l--){ int p,t;cin>>p>>t; tr->dry(); for (int i=0;ipour_at(taps[i].first,taps[i].second*t); printf("%.5f\n",tr->height_at(p)); } delete tr; } }