#include #include #include #include #include #include #include using namespace std; typedef double CoordType; const CoordType pi180 = acos(-1) / 180; struct Point; struct Transform; struct Figure; struct Bounds; struct Point { CoordType x, y; Point() : x(0), y(0) {} Point(CoordType x_, CoordType y_) : x(x_), y(y_) {} CoordType distance(const Point& o) const { auto dx = x - o.x, dy = y - o.y; auto len = sqrt(dx * dx + dy * dy); return len; } Point transform(const Transform* t) const; static CoordType sign(const Point& p1, const Point& p2, const Point& p3) { return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y); } bool isInTriangle(const Point& p1, const Point& p2, const Point& p3) { CoordType d1, d2, d3; bool has_neg, has_pos; d1 = sign((*this), p1, p2); d2 = sign((*this), p2, p3); d3 = sign((*this), p3, p1); has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0); has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0); return !(has_neg && has_pos); } }; struct Transform : Point { CoordType a; Transform() : a(0) {} Transform(CoordType x, CoordType y, CoordType a_) : Point(x, y), a(a_) {} Point apply(const Point& i) const { CoordType cosa = cos(a * pi180); CoordType sina = sin(a * pi180); return Point(cosa * i.x - sina * i.y + x, sina * i.x + cosa * i.y + y); } }; struct Bounds { Point min, max, center; CoordType radius; void clear() { min = Point(+numeric_limits::max(), +numeric_limits::max()); max = Point(-numeric_limits::max(), -numeric_limits::max()); center = Point(); radius = -1; } void calc(const vector& points, const Transform* transform = nullptr); CoordType w() const { return max.x - min.x; } CoordType h() const { return max.y - min.y; } }; struct Figure { vector points; vector> convexes; CoordType face; void calcFace(); CoordType calcTriFace(int i1, int i2, int i3) const; static CoordType calcTriFace(const Point& p1, const Point& p2, const Point& p3); static CoordType calcTriFaceSign(const Point& p1, const Point& p2, const Point& p3); void calcBounds(); static bool intersect(const Figure& lf, const Figure& rf, const Transform* lt, const Transform* rt); CoordType calcAngle(); }; struct Pair { int s, e; Pair() : s(0), e(0) {} Pair(int s_, int e_) : s(s_), e(e_) {} }; void Figure::calcFace() { face = 0; for (int c = 0; c < (int)convexes.size(); c++) { vector const& indices = convexes[c]; for (int i = 2; i < (int)indices.size(); i++) { face += calcTriFace(indices[0], indices[i - 1], indices[i]); } } } CoordType Figure::calcTriFace(int i1, int i2, int i3) const { return calcTriFace(points[i1], points[i2], points[i3]); } CoordType Figure::calcTriFace(const Point& p1, const Point& p2, const Point& p3) { return abs(calcTriFaceSign(p1, p2, p3)) / 2; } CoordType Figure::calcTriFaceSign(const Point& p1, const Point& p2, const Point& p3) { return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p1.x * p3.y - p2.x * p1.y - p3.x * p2.y; } CoordType Figure::calcAngle() { int pc = (int)points.size(); CoordType ix = 0, iy = 0; for (int p = 0; p < pc; p++) { const auto& pt = points[p]; ix += pt.x; iy += pt.y; } ix /= pc; iy /= pc; CoordType ixx = 0, iyy = 0, ixy = 0; for (int p = 0; p < (int)points.size(); p++) { const auto& pt = points[p]; auto dx = pt.x - ix, dy = pt.y - iy; ixx += dy * dy; iyy += dx * dx; ixy -= dx * dy; } auto a = (ixx + iyy) / 2, b = (ixx - iyy) / 2; auto l = a - sqrt(b * b + ixy * ixy); cout << atan2(ixy, ixx - l) << " " << atan2(iyy - l, ixy) << endl; auto c = 90 - atan2(ixy, ixx - l) / pi180; if (c < 0) c += 360; return c; } void Bounds::calc(const vector& points, const Transform* t) { int pc = (int)points.size(); clear(); if (pc > 0) { for (int p = 0; p < pc; p++) { Point pt = points[p].transform(t); if (min.x > pt.x) min.x = pt.x; if (min.y > pt.y) min.y = pt.y; if (max.x < pt.x) max.x = pt.x; if (max.y < pt.y) max.y = pt.y; center.x += pt.x; center.y += pt.y; } center.x /= pc; center.y /= pc; for (int p = 0; p < pc; p++) { Point pt = points[p].transform(t); auto len = center.distance(pt); if (radius < len) radius = len; } } } bool Figure::intersect(const Figure& lf, const Figure& rf, const Transform* lt, const Transform* rt) { int lpc = (int)lf.points.size(); vector lp(lpc); for (int p = 0; p < lpc; p++) lp[p] = lf.points[p].transform(lt); int rpc = (int)rf.points.size(); vector rp(rpc); for (int p = 0; p < lpc; p++) rp[p] = rf.points[p].transform(rt); for (const auto& p : rp) { for (const auto& c : lf.convexes) { auto sf0 = calcTriFaceSign(lp[c[0]], lp[c[1]], p); for (int i = 2, ic = (int)c.size(); i < ic; i++) { auto sf1 = calcTriFaceSign(lp[c[i - 1]], lp[c[i]], p); if (sf0 * sf1 < 0) return true; } } } return false; } Point Point::transform(const Transform* t) const { return t ? t->apply(*this) : *this; } static ifstream& operator >>(ifstream& fin, Figure& f) { int numPoints; fin >> numPoints; f.points.resize(numPoints); for (int p = 0; p < numPoints; p++) fin >> f.points[p].x >> f.points[p].y; int numConvexes; fin >> numConvexes; f.convexes.resize(numConvexes); for (int c = 0; c < numConvexes; c++) { int numIndices; fin >> numIndices; vector& indices = f.convexes[c]; indices.resize(numIndices); for (int i = 0; i < numIndices; i++) fin >> indices[i]; } return fin; } CoordType CalcWidthAtAngle(const Figure& f, CoordType angle) { Transform t(0, 0, angle); Bounds b; b.clear(); b.calc(f.points, &t); return b.w(); } CoordType GetMinWidthAngle(const Figure& f, CoordType w, CoordType angle, CoordType delta) { auto wl = CalcWidthAtAngle(f, angle - delta); if (wl < w) { if (delta < 1) return angle - delta; else return GetMinWidthAngle(f, wl, angle - delta, delta / 2); } auto wr = CalcWidthAtAngle(f, angle + delta); if (wr < w) { if (delta < 1) return angle + delta; else return GetMinWidthAngle(f, wr, angle + delta, delta / 2); } return angle; } void LinearOrder(const vector
& figures, vector& bounds, vector& trans) { int numFigures = (int)figures.size(); for (int f = 0; f < numFigures; f++) { const auto& b = bounds[f]; if (b.w() > b.h()) trans[f].a = GetMinWidthAngle(figures[f], b.h(), 90, 45); else trans[f].a = GetMinWidthAngle(figures[f], b.w(), 180, 45); //trans[f].a = figures[f].calcAngle(); bounds[f].calc(figures[f].points, &trans[f]); } vector order(numFigures); for (int i = 0; i < numFigures; i++) order[i] = i; //sort(order.begin(), order.end(), [&bounds](int l, int r) -> bool { return bounds[l].w() < bounds[r].w(); }); sort(order.begin(), order.end(), [&bounds](int l, int r) -> bool { return bounds[l].h() < bounds[r].h(); }); CoordType offset = 0; for (int f = 0; f < numFigures; f++) { int ind = order[f]; trans[ind].x = offset - bounds[ind].min.x; trans[ind].y = -bounds[ind].min.y; offset += bounds[ind].w() * 1.01; cout << ind << " " << trans[ind].x << " " << bounds[ind].min.x << " " << offset << " " << bounds[ind].w() << endl; } } struct RadialOrder { const vector
& figures; const vector& bounds; vector& trans; vector order; RadialOrder(const vector
& figures_, vector& bounds_, vector& trans_) : figures(figures_) , bounds(bounds_) , trans(trans_) , order(figures_.size()) { int numFigures = (int)figures.size(); for (int i = 0; i < numFigures; i++) order[i] = i; sort(order.begin(), order.end(), [this](int l, int r) -> bool { return bounds[l].radius > bounds[r].radius; }); } void CalcTransform(int s, int e, int n) { Point ps = bounds[s].center.transform(&trans[s]); Point pe = bounds[e].center.transform(&trans[e]); auto lse = bounds[s].radius + bounds[e].radius; auto lsn = bounds[s].radius + bounds[n].radius; auto len = bounds[e].radius + bounds[n].radius; auto lse2 = ps.distance(pe); auto ca = (lse * lse + lsn * lsn - len * len) / (2 * lse * lsn); auto sa = sqrt(1 - ca * ca); auto lsex = pe.x - ps.x; auto lsey = pe.y - ps.y; auto lsnx = lsex * ca - lsey * sa; auto lsny = lsex * sa + lsey * ca; trans[n].x = ps.x + lsnx * lsn / lse - bounds[n].center.x; trans[n].y = ps.y + lsny * lsn / lse - bounds[n].center.y; bool issn = Figure::intersect(figures[s], figures[n], &trans[s], &trans[n]); bool isen = Figure::intersect(figures[e], figures[n], &trans[e], &trans[n]); bool isse = Figure::intersect(figures[s], figures[e], &trans[s], &trans[e]); } void ProcessPairs(const vector& pairs, int l, int f, int numF) { vector next(pairs.size() * 1); int o = 0; for (const auto& p : pairs) { if (++f < numF) { int i = order[f]; if (l % 2) next[o++] = Pair(p.s, i); else next[o++] = Pair(i, p.e); CalcTransform(p.s, p.e, i); } else break; } if (f < numF) ProcessPairs(next, l + 1, f, numF); } void solve() { int i0 = order[0], i1 = order[1]; trans[i0].x = -bounds[i0].center.x; trans[i0].y = -bounds[i0].center.y; trans[i1].x = bounds[i0].radius + bounds[i1].radius - bounds[i1].center.x; trans[i1].y = -bounds[i1].center.y; vector pairs(2); pairs[0] = Pair(i0, i1); pairs[1] = Pair(i1, i0); bool is01 = Figure::intersect(figures[i0], figures[i1], &trans[i0], &trans[i1]); ProcessPairs(pairs, 1, 1, (int)figures.size()); } }; //#define INFILE "00.in" #define INFILE "packing.in" #define OUTFILE "packing.out" int main() { ifstream fin(INFILE); int numFigures; fin >> numFigures; vector
figures(numFigures); vector bounds(numFigures); for (int f = 0; f < numFigures; f++) { fin >> figures[f]; bounds[f].calc(figures[f].points); figures[f].calcFace(); } vector trans(numFigures); LinearOrder(figures, bounds, trans); //RadialOrder(figures, bounds, trans).solve(); ofstream fout(OUTFILE); fout << setprecision(6); for (int f = 0; f < numFigures; f++) { fout << "1 " << trans[f].a << " " << trans[f].x << " " << trans[f].y << endl; } }