#include using namespace std; const int MAX_F = 507; const int MAX_P = 107; const int MAX_M = 107; const long double PI = acos(-1); const long double inf = 1e6; class point{ public: long double x, y; point(){} void rotate(long double deg){ long double angle = PI / (long double)180.0 * deg; //angle = -angle; long double s = sin(angle); long double c = cos(angle); long double newx = x * c - y * s; long double newy = x * s + y * c; x = newx; y = newy; } void normalise(){ long double t = (long double)sqrt((long double)x * x + y * y); x /= (long double)t; y /= (long double)t; } }; typedef point line; struct figure{ int m, p, k[MAX_M]; vector idx[MAX_M]; point pnt[MAX_P]; point mn, mx; int fig_idx; figure(){} void rotate(long double deg){ for(int i = 0; i < p; ++i){ pnt[i].rotate(deg); } } void calc_min_max(){ mn = mx = pnt[0]; for(int j = 1; j < p; ++j){ mn.x = min(mn.x, pnt[j].x); mn.y = min(mn.y, pnt[j].y); mx.x = max(mx.x, pnt[j].x); mx.y = max(mx.y, pnt[j].y); } } void add_to_y(long double add){ mn.y -= add; } }; bool cmp_figure(figure lvalue, figure rvalue){ return (lvalue.mx.y - lvalue.mn.y) < (rvalue.mx.y - rvalue.mn.y); } long double triangle_sum(point a, point b, point c){ return (a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y); } int f; figure fig[MAX_F]; point pos[MAX_F]; long double rot[MAX_F]; void input(){ ios::sync_with_stdio(false); cin.tie(NULL); freopen("packing.in", "r", stdin); freopen("packing.out", "w", stdout); cin >> f; for(int i = 0; i < f; ++i){ cin >> fig[i].p; for(int j = 0; j < fig[i].p; ++j){ cin >> fig[i].pnt[j].x >> fig[i].pnt[j].y; } cin >> fig[i].m; for(int j = 0; j < fig[i].m; ++j){ cin >> fig[i].k[j]; for(int j2 = 0; j2 < fig[i].k[j]; ++j2){ int t; cin >> t; fig[i].idx[j].push_back(t); } } fig[i].fig_idx = i; } } void rotate_figures(){ for(int i = 0; i < f; ++i){ fig[i].calc_min_max(); long double best_deg = 0, best_diff = fig[i].mx.y - fig[i].mn.y; for(int j = 1; j <= 360; ++j){ figure tmp = fig[i]; tmp.rotate(j); tmp.calc_min_max(); long double curr_diff = tmp.mx.y - tmp.mn.y; if(curr_diff < best_diff){ best_diff = curr_diff; best_deg = (long double)j; } } rot[i] = best_deg; fig[i].rotate(best_deg); fig[i].calc_min_max(); } } bool clockwise(point a, point b, point c){ return (a.x * b.y + b.x * c.y + c.x * a.y) > (a.x * c.y + b.x * a.y + c.x * b.y); } bool intersect(point a, point b, point c, point d){ return (clockwise(a, c, d) != clockwise(b, c, d)) && (clockwise(a, b, c) != clockwise(a, b, d)); } long double get_max_pull(const figure f_prev, const figure f_curr){ long double ll = 0, rr = f_prev.mx.x - f_prev.mn.x; while ((rr - ll) > 0.0000002){ long double mid = (ll + rr) / (long double)2.0; bool ok = true; vector > edges1, edges2; if(f_prev.mx.x + mid > f_curr.mx.x && f_prev.mn.x + mid < f_curr.mn.x){ if(f_prev.mx.y > f_curr.mx.y && f_prev.mn.y < f_curr.mn.y){ rr = mid; continue; } } for(int j1 = 0; j1 < f_prev.m; ++j1){ for(int j3 = 0; j3 < (int)f_prev.idx[j1].size(); ++j3){ int nxt = (j3 + 1) % (int)f_prev.idx[j1].size(); point a = f_prev.pnt[ f_prev.idx[j1][j3] ]; point b = f_prev.pnt[ f_prev.idx[j1][nxt] ]; a.x -= f_prev.mn.x; a.y -= f_prev.mn.y; b.x -= f_prev.mn.x; b.y -= f_prev.mn.y; edges1.push_back({a, b}); } } for(int j1 = 0; j1 < f_curr.m; ++j1){ for(int j3 = 0; j3 < (int)f_curr.idx[j1].size(); ++j3){ int nxt = (j3 + 1) % (int)f_curr.idx[j1].size(); point a = f_curr.pnt[ f_curr.idx[j1][j3] ]; point b = f_curr.pnt[ f_curr.idx[j1][nxt] ]; a.x -= f_curr.mn.x; a.y -= f_curr.mn.y; b.x -= f_curr.mn.x; b.y -= f_curr.mn.y; a.x += f_prev.mx.x - f_prev.mn.x - mid; b.x += f_prev.mx.x - f_prev.mn.x - mid; edges2.push_back({a, b}); } } long double mx = 0; for(pair e1: edges1){ for(pair e2: edges2){ if(intersect(e1.first, e1.second, e2.first, e2.second)){ ok = false; break; } } if(!ok){ break; } } if(ok){ ll = mid; } else{ rr = mid; } } if(ll > 0.001){ ll -= 0.001; } else{ ll = 0; } return ll; } void remove_empty_space(){ /* http://web.archive.org/web/20141127210836/http://content.gpwiki.org/index.php/Polygon_Collision */ long double curr_x = 0.0f, curr_y = 0.0f; for(int i = 0; i < f; ++i){ if(i == 0){ pos[fig[i].fig_idx].x = (long double)curr_x + (long double)-fig[i].mn.x; pos[fig[i].fig_idx].y = (long double)-fig[i].mn.y; curr_x += fig[i].mx.x - fig[i].mn.x; } else{ long double pull = get_max_pull(fig[i - 1], fig[i]), add_rot = 0, add_y = 0; figure prev = fig[i]; vector > v = {{0, (long double)0.001f}, {0, (long double)-0.001f}, {180, (long double)0.001f}, {180, (long double)-0.001f}}; for(pair p: v){ figure tmp_f = prev; tmp_f.rotate(p.first); tmp_f.calc_min_max(); tmp_f.add_to_y(p.second); long double curr_pull = get_max_pull(fig[i - 1], tmp_f); if(pull < curr_pull){ pull = curr_pull; add_rot = p.first; add_y = p.second; fig[i] = tmp_f; } } rot[fig[i].fig_idx] += add_rot; if(rot[fig[i].fig_idx] >= 360){ rot[fig[i].fig_idx] -= 360; } fig[i].mn.y += add_y; curr_y += add_y; pos[fig[i].fig_idx].x = (long double)curr_x + (long double)-fig[i].mn.x - pull; pos[fig[i].fig_idx].y = (long double)-fig[i].mn.y + curr_y; curr_x += fig[i].mx.x - fig[i].mn.x - pull; } } } void solve(){ rotate_figures(); sort(fig, fig + f, cmp_figure); remove_empty_space(); } void output(){ for(int i = 0; i < f; ++i){ cout << "1 " << fixed << setprecision(6) << rot[i] << " " << pos[i].x << " " << pos[i].y << "\n"; } } int main(){ input(); solve(); output(); }