/* [NWERC'07] WALK by: Jan Kuipers */ using namespace std; #include #include #include const double eps = 1e-9; int main () { int runs; cin>>runs; while (runs--) { int N; cin>>N; vector h(N),n(N); vector > > p(N); for (int i=0; i>h[i]>>n[i]; p[i]=vector >(n[i]); for (int j=0; j>p[i][j].first>>p[i][j].second; p[i].push_back(p[i][0]); } vector > cross; for (int i=0; i 0) continue; double x = p[i][j].first + 1.0*(p[i][j+1].first-p[i][j].first)/(p[i][j+1].second-p[i][j].second) * -p[i][j].second; if (x>0 && x<100000) cross.push_back(make_pair(x,i)); } sort(cross.begin(),cross.end()); stack s; for (int i=0; i0) desc+=diff; else asc-=diff; last=s.top(); s.pop(); } cout<