#include #include #include #include #include #include #include #define fi first #define se second #define ap all_points #define ch convex_hull using namespace std; const int MAXF = 512; const double EPS = 0.0000000001; const double PI = 3.14159265; struct point { double x, y; point(){} point(double x, double y) { this -> x = x; this -> y = y; } }; struct figure { int p, m; // number of points and polygons int idx; // index of the figure bool use; double dx, dy, minx, maxx, miny, maxy; // dimensions of the figure double x_shift, y_shift, angle; // translation and rotation vector points; vector> polygons; }; FILE *inp, *out; int f; figure a[MAXF]; vector all_points; vector convex_hull; int compfig; double cross_product(point A, point B, point C) { double x1 = B.x - A.x, y1 = B.y - A.y; double x2 = C.x - A.x, y2 = C.y - A.y; return x1 * y2 - x2 * y1; } double dot_product(point A, point B, point C) { double x1 = B.x - A.x, y1 = B.y - A.y; double x2 = C.x - A.x, y2 = C.y - A.y; return x1 * x2 + y1 * y2; } double dist(point A, point B) { double x = A.x - B.x, y = A.y - B.y; return sqrt(x * x + y * y); } bool comp_yxi(int aidx, int bidx) { point A = a[compfig].points[aidx]; point B = a[compfig].points[bidx]; if (A.y != B.y) return A.y > B.y; else return A.x < B.x; } bool comp_yxp(point A, point B) { if (A.y != B.y) return A.y > B.y; else return A.x < B.x; } bool comp_points(point A, point B) { double cp = cross_product(ap[0], A, B); if (fabs(cp) > EPS) return cp > EPS; else return dist(ap[0], A) < dist(ap[0], B); } bool comp_figures(figure A, figure B) { return A.dy > B.dy; } bool comp_original(figure A, figure B) { return A.idx < B.idx; } void Init() { inp = fopen("packing.in", "r"); out = fopen("packing.out", "w"); fscanf(inp, "%d", &f); for (int i = 1; i <= f; ++ i) { fscanf(inp, "%d", &a[i].p); for (int j = 1; j <= a[i].p; ++ j) { double x, y; fscanf(inp, "%lf%lf", &x, &y); a[i].points.emplace_back(x, y); if (j == 1) { a[i].minx = a[i].maxx = x; a[i].miny = a[i].maxy = y; } else { a[i].minx = min(x, a[i].minx); a[i].maxx = max(x, a[i].maxx); a[i].miny = min(y, a[i].miny); a[i].maxy = max(y, a[i].maxy); } } a[i].dx = a[i].maxx - a[i].minx; a[i].dy = a[i].maxy - a[i].miny; fscanf(inp, "%d", &a[i].m); a[i].polygons.resize(a[i].m); for (int j = 1; j <= a[i].m; ++ j) { int l; fscanf(inp, "%d", &l); for (int k = 1; k <= l; ++ k) { int idx; fscanf(inp, "%d", &idx); a[i].polygons[j - 1].push_back(idx); } } a[i].idx = i; a[i].use = true; } } bool is_between(double x, double y, double z) { if (x <= y and y <= z) return true; if (z <= y and y <= x) return true; return false; } bool is_inside(figure F, point P) { for (int i = 0; i < F.m; ++ i) { bool fl = true; int idx, jdx; point Aprim, Bprim; double minp = 0, maxp = 0; for (int j = 0; j < F.polygons[i].size(); ++ j) { idx = F.polygons[i][j]; jdx = F.polygons[i][(j + 1 == F.polygons[i].size()) ? 0 : j + 1]; Aprim = {F.points[idx].x + F.x_shift, F.points[idx].y + F.y_shift}; Bprim = {F.points[jdx].x + F.x_shift, F.points[jdx].y + F.y_shift}; double cp = cross_product(Aprim, Bprim, P); minp = min(minp, cp); maxp = max(maxp, cp); if (minp < -EPS and maxp > +EPS) { fl = false; break; } } if (fl) { return true; } } return false; } bool intersect(point A, point B, point C, point D) { double cp1 = cross_product(A, B, C), cp2 = cross_product(A, B, D); double cp3 = cross_product(C, D, A), cp4 = cross_product(C, D, B); if (cp1 == 0 and is_between(A.x, C.x, B.x) and is_between(A.y, C.y, B.y)) return true; if (cp2 == 0 and is_between(A.x, D.x, B.x) and is_between(A.y, D.y, B.y)) return true; if (cp3 == 0 and is_between(C.x, A.x, D.x) and is_between(C.y, A.y, D.y)) return true; if (cp4 == 0 and is_between(C.x, B.x, D.x) and is_between(C.y, B.y, D.y)) return true; if (cp1 * cp2 < 0 and cp3 * cp4 < 0) return true; else return false; } bool intersect(figure A, figure B) { for (int i = 0; i < A.m; ++ i) { for (int ii = 0; ii < A.polygons[i].size(); ++ ii) { for (int j = 0; j < B.m; ++ j) { for (int jj = 0; jj < B.polygons[j].size(); ++ jj) { point A1 = A.points[A.polygons[i][ii]]; point A2 = A.points[A.polygons[i][(ii + 1) % A.polygons[i].size()]]; point B1 = B.points[B.polygons[j][jj]]; point B2 = B.points[B.polygons[j][(jj + 1) % B.polygons[j].size()]]; A1.x += A.x_shift; A1.y += A.y_shift; A2.x += A.x_shift; A2.y += A.y_shift; B1.x += B.x_shift; B1.y += B.y_shift; B2.x += B.x_shift; B2.y += B.y_shift; if (intersect(A1, A2, B1, B2)) { return true; } } } } } point Aprim = {A.points[0].x + A.x_shift, A.points[0].y + A.y_shift}; point Bprim = {B.points[0].x + B.x_shift, B.points[0].y + B.y_shift}; if (is_inside(A, Bprim) or is_inside(B, Aprim)) return true; else return false; } double Evaluate() { ap.resize(0); for (int i = 1; i <= f; ++ i) { for (auto p : a[i].points) { ap.emplace_back(p.x + a[i].x_shift, p.y + a[i].y_shift); } } for (int i = 1; i < ap.size(); ++ i) { if (ap[i].y < ap[0].y or (ap[i].y == ap[0].y and ap[i].x < ap[0].x)) { swap(ap[i], ap[0]); } } sort(++ap.begin(), ap.end(), comp_points); ch.push_back(ap[0]); ch.push_back(ap[1]); for (int i = 2; i < ap.size(); ++ i) { while (cross_product(ch[ch.size() - 2], ch[ch.size() - 1], ap[i]) < -EPS) { ch.pop_back(); } ch.push_back(ap[i]); } // for (int i = 0; i < ap.size(); ++ i) // { // cerr << ap[i].x << ' ' << ap[i].y << endl; // } // cerr << "----------" << endl; // for (int i = 0; i < ch.size(); ++ i) // { // cerr << ch[i].x << ' ' << ch[i].y << endl; // } double area = 0; for (int i = 2; i < ch.size(); ++ i) { area += cross_product(ch[0], ch[i - 1], ch[i]); } return area / 2; } void Print() { sort(a + 1, a + f + 1, comp_original); for (int i = 1; i <= f; ++ i) { if (a[i].use == 0) fprintf(out, "0\n"); else fprintf(out, "1 %6f %.6f %.6f\n", a[i].angle, a[i].x_shift, a[i].y_shift); } } void Rotate(int idx) { double phi = a[idx].angle / 180 * PI; for (int i = 0; i < a[idx].points.size(); ++ i) { double xprim = a[idx].points[i].x * cos(phi) - a[idx].points[i].y * sin(phi); double yprim = a[idx].points[i].x * sin(phi) + a[idx].points[i].y * cos(phi); a[idx].points[i] = {xprim, yprim}; } a[idx].minx = a[idx].maxx = a[idx].points[0].x; a[idx].miny = a[idx].maxy = a[idx].points[0].y; for (int i = 1; i < a[idx].points.size(); ++ i) { a[idx].minx = min(a[idx].minx, a[idx].points[i].x); a[idx].maxx = max(a[idx].maxx, a[idx].points[i].x); a[idx].miny = min(a[idx].miny, a[idx].points[i].y); a[idx].maxy = max(a[idx].maxy, a[idx].points[i].y); } } void SolveTetromino() { for (int i = 1; i <= f; ++ i) { if (a[i].m != 4) return; for (int j = 0; j < 4; ++ j) { if (a[i].polygons[j].size() != 4) return; for (int p = 0; p < 4; ++ p) { int pidx = a[i].polygons[j][p], qidx, br = 0; for (int q = 0; q < 4; ++ q) { qidx = a[i].polygons[j][q]; if (a[i].points[pidx].x == a[i].points[qidx].x and fabs(a[i].points[pidx].y - a[i].points[qidx].y) == 1) br += 1; if (a[i].points[pidx].y == a[i].points[qidx].y and fabs(a[i].points[pidx].x - a[i].points[qidx].x) == 1) br += 2; } if (br != 3) return; } } } cerr << "special case: tetromino" << endl; vector O, I, T, Z, S, L, J; for (int i = 1; i <= f; ++ i) { vector v; for (int j = 0; j < 4; ++ j) { compfig = i; sort(a[i].polygons[j].begin(), a[i].polygons[j].end(), comp_yxi); v.push_back(a[i].points[a[i].polygons[j][0]]); } sort(v.begin(), v.end(), comp_yxp); // check for O if (v[0].x + 1 == v[1].x and v[1].x - 1 == v[2].x and v[2].x + 1 == v[3].x and v[0].y == v[1].y and v[1].y - 1 == v[2].y and v[2].y == v[3].y) O.push_back(i); // check for I if (v[0].x + 1 == v[1].x and v[1].x + 1 == v[2].x and v[2].x + 1 == v[3].x and v[0].y == v[1].y and v[1].y == v[2].y and v[2].y == v[3].y) I.push_back(i); if (v[0].x == v[1].x and v[1].x == v[2].x and v[2].x == v[3].x and v[0].y - 1 == v[1].y and v[1].y - 1 == v[2].y and v[2].y - 1 == v[3].y) {a[i].angle = 90; I.push_back(i);} // check for Z if (v[0].x + 1 == v[1].x and v[1].x == v[2].x and v[2].x + 1 == v[3].x and v[0].y == v[1].y and v[1].y - 1 == v[2].y and v[2].y == v[3].y) Z.push_back(i); if (v[0].x - 1 == v[1].x and v[0].x == v[2].x and v[1].x == v[3].x and v[0].y - 1 == v[1].y and v[1].y == v[2].y and v[2].y - 1 == v[3].y) {a[i].angle = 90; Z.push_back(i);} // check for S if (v[0].x + 1 == v[1].x and v[0].x - 1 == v[2].x and v[0].x == v[3].x and v[0].y == v[1].y and v[1].y - 1 == v[2].y and v[2].y == v[3].y) S.push_back(i); if (v[0].x == v[1].x and v[1].x + 1 == v[2].x and v[2].x == v[3].x and v[0].y - 1 == v[1].y and v[1].y == v[2].y and v[2].y - 1 == v[3].y) {a[i].angle = 90; S.push_back(i);} // check for T if (v[0].x + 1 == v[1].x and v[1].x + 1 == v[2].x and v[3].x == v[1].x and v[0].y == v[1].y and v[1].y == v[2].y and v[2].y - 1 == v[3].y) T.push_back(i); if (v[0].x - 1 == v[1].x and v[0].x == v[2].x and v[0].x == v[3].x and v[0].y - 1 == v[1].y and v[1].y == v[2].y and v[2].y - 1 == v[3].y) {a[i].angle = 90; T.push_back(i);} if (v[0].x == v[2].x and v[1].x + 1 == v[2].x and v[2].x + 1 == v[3].x and v[0].y - 1 == v[1].y and v[1].y == v[2].y and v[2].y == v[3].y) {a[i].angle = 180; T.push_back(i);} if (v[0].x == v[1].x and v[1].x == v[3].x and v[1].x + 1 == v[2].x and v[0].y - 1 == v[1].y and v[1].y == v[2].y and v[2].y - 1 == v[3].y) {a[i].angle = 270; T.push_back(i);} // check for L if (v[0].x == v[3].x and v[0].x + 1 == v[1].x and v[1].x + 1 == v[2].x and v[0].y == v[1].y and v[1].y == v[2].y and v[2].y - 1 == v[3].y) L.push_back(i); if (v[0].x + 1 == v[1].x and v[1].x == v[2].x and v[2].x == v[3].x and v[0].y == v[1].y and v[1].y - 1 == v[2].y and v[2].y - 1 == v[3].y) {a[i].angle = 90; L.push_back(i);} if (v[0].x - 2 == v[1].x and v[1].x + 1 == v[2].x and v[2].x + 1 == v[3].x and v[0].y - 1 == v[1].y and v[1].y == v[2].y and v[2].y == v[3].y) {a[i].angle = 180; L.push_back(i);} if (v[0].x == v[1].x and v[1].x == v[2].x and v[2].x + 1 == v[3].x and v[0].y - 1 == v[1].y and v[1].y - 1 == v[2].y and v[2].y == v[3].y) {a[i].angle = 270; L.push_back(i);} // check for J if (v[0].x == v[1].x and v[1].x + 1 == v[2].x and v[2].x + 1 == v[3].x and v[0].y - 1 == v[1].y and v[1].y == v[2].y and v[2].y == v[3].y) J.push_back(i); if (v[0].x + 1 == v[1].x and v[0].x == v[2].x and v[0].x == v[3].x and v[0].y == v[1].y and v[1].y - 1 == v[2].y and v[2].y - 1 == v[3].y) {a[i].angle = 90; J.push_back(i);} if (v[0].x + 1 == v[1].x and v[1].x + 1 == v[2].x and v[2].x == v[3].x and v[0].y == v[1].y and v[1].y == v[2].y and v[2].y - 1 == v[3].y) {a[i].angle = 180; J.push_back(i);} if (v[0].x == v[1].x and v[1].x == v[3].x and v[1].x - 1 == v[2].x and v[0].y - 1 == v[1].y and v[1].y - 1 == v[2].y and v[2].y == v[3].y) {a[i].angle = 270; J.push_back(i);} } // for (int x : O) cerr << x << ' '; cout << endl; // for (int x : I) cerr << x << ' '; cout << endl; // for (int x : T) cerr << x << ' '; cout << endl; // for (int x : Z) cerr << x << ' '; cout << endl; // for (int x : S) cerr << x << ' '; cout << endl; // for (int x : L) cerr << x << ' '; cout << endl; // for (int x : J) cerr << x << ' '; cout << endl; double xx = 0; for (int i = 0; i < O.size(); ++ i) { a[O[i]].x_shift = xx - a[O[i]].minx; a[O[i]].y_shift = -a[O[i]].miny; xx += 2.001; } for (int i = 0; i < I.size(); i += 2) { Rotate(I[i]); a[I[i]].x_shift = xx - a[I[i]].minx; a[I[i]].y_shift = -a[I[i]].miny; if (i + 1 < I.size()) { Rotate(I[i + 1]); a[I[i + 1]].x_shift = xx - a[I[i + 1]].minx; a[I[i + 1]].y_shift = -a[I[i + 1]].miny + 1.001; } xx += 4.001; } for (int i = 0; i < L.size(); i += 2) { Rotate(L[i]); a[L[i]].x_shift = xx - a[L[i]].minx; a[L[i]].y_shift = -a[L[i]].miny; if (i + 1 < L.size()) { a[L[i + 1]].angle = a[L[i + 1]].angle + 180; if (a[L[i + 1]].angle >= 360) a[L[i + 1]].angle -= 360; Rotate(L[i + 1]); a[L[i + 1]].x_shift = xx - a[L[i + 1]].minx + 1.001; a[L[i + 1]].y_shift = -a[L[i + 1]].miny - 0.001; } if (i + 1 < L.size()) xx += 4.002; else xx += 3.001; } for (int i = 0; i < J.size(); i += 2) { Rotate(J[i]); a[J[i]].x_shift = xx - a[J[i]].minx; a[J[i]].y_shift = -a[J[i]].miny; if (i + 1 < J.size()) { a[J[i + 1]].angle = a[J[i + 1]].angle + 180; if (a[J[i + 1]].angle >= 360) a[J[i + 1]].angle -= 360; Rotate(J[i + 1]); a[J[i + 1]].x_shift = xx - a[J[i + 1]].minx + 1.001; a[J[i + 1]].y_shift = -a[J[i + 1]].miny + 0.001; } if (i + 1 < J.size()) xx += 4.002; else xx += 3.001; } if (J.size() % 2) xx -= 1; for (int i = 0; i < T.size(); i += 2) { Rotate(T[i]); a[T[i]].x_shift = xx - a[T[i]].minx; a[T[i]].y_shift = -a[T[i]].miny + 0.001; if (i + 1 < T.size()) { a[T[i + 1]].angle = a[T[i + 1]].angle + 180; if (a[T[i + 1]].angle >= 360) a[T[i + 1]].angle -= 360; Rotate(T[i + 1]); a[T[i + 1]].x_shift = xx - a[T[i + 1]].minx + 2.001; a[T[i + 1]].y_shift = -a[T[i + 1]].miny; } if (i + 1 < T.size()) xx += 4.002; else xx += 3.001; } if (T.size() % 2) xx -= 1; else xx += 1; for (int i = 0; i < S.size(); ++ i) { Rotate(S[i]); a[S[i]].x_shift = xx - a[S[i]].minx; a[S[i]].y_shift = -a[S[i]].miny - (i + 1) * 0.001; xx += 2.001; } xx += 1; for (int i = 0; i < Z.size(); ++ i) { Rotate(Z[i]); a[Z[i]].x_shift = xx - a[Z[i]].minx; a[Z[i]].y_shift = -a[Z[i]].miny + (i + 1) * 0.001; xx += 2.001; } // for (int i = 0; i < O.size(); ++ i) a[O[i]].use = 0; // for (int i = 0; i < I.size(); ++ i) a[I[i]].use = 0; // for (int i = 0; i < L.size(); ++ i) a[L[i]].use = 0; // for (int i = 0; i < J.size(); ++ i) a[J[i]].use = 0; // for (int i = 0; i < T.size(); ++ i) a[T[i]].use = 0; // for (int i = 0; i < S.size(); ++ i) a[S[i]].use = 0; // for (int i = 0; i < Z.size(); ++ i) a[Z[i]].use = 0; Print(); exit(0); } int main() { Init(); SolveTetromino(); sort(a + 1, a + f + 1, comp_figures); double xx = 0; for (int i = 1; i <= f; ++ i) { a[i].y_shift = -a[i].miny - a[i].dy / 2; a[i].angle = 0; double l = xx - a[i].minx - a[i - 1].dx; double r = xx - a[i].minx, res = 0; while (r - l > EPS) { double mid = (l + r) / 2; a[i].x_shift = mid; if (intersect(a[i], a[i - 1]) == 0) { res = mid; r = mid - EPS; } else l = mid + EPS; } a[i].x_shift = res + 0.001; // if (i != 1) // { // if (intersect(a[i - 1], a[i])) // { // cerr << "Intersection!!! " << i - 1 << ' ' << i << endl; // while (true); // return 0; // } // } xx = a[i].maxx + a[i].x_shift + 0.001; /// } Print(); cerr << "Evaluation: " << Evaluate() << endl; return 0; }