Submission #1245245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245245		countless	Scissors and Tape (CEOI19_scissors)	C++20	100 / 100	2 ms	328 KiB

scissors

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

const ld EPS = 1e-3;

struct Point {
    ld x, y;
    
    Point(ld x = 0, ld y = 0) : x(x), y(y) {;;}

    bool operator==(Point p) const { return tie(x, y) == tie(p.x, p.y); }

    Point operator+(Point p) const { return Point(x+p.x, y+p.y); }
    Point operator-(Point p) const { return Point(x-p.x, y-p.y); }
    Point operator*(ld d) const { return Point(x*d, y*d); }
    Point operator/(ld d) const { return Point(x/d, y/d); }

    ld dist2() const { return x*x + y*y; }
    ld dist() const { return sqrtl(dist2()); }

    ld dot(Point p) const { return x*p.x + y*p.y; }
    ld angle() const { return atan2(y, x); }

    ld cross(Point p) const { return x*p.y - y*p.x; }
    ld cross(Point a, Point b) const { return (a-*this).cross(b-*this); }

    Point unit() const { return *this/dist(); }
    Point rotate(ld a) const { return Point(x*cos(a)-y*sin(a), x*sin(a)+y*cos(a)); }

    friend ostream& operator<<(ostream &os, Point p) {
        // return os << "(" << p.x << ", " << p.y << ")";
        return os << p.x << " " << p.y;
    }
};

struct Polygon {
    int id;
    vector<Point> poly;

    Polygon(int id = -1) : id(id) {;;}

    void input(ll sz) { 
        while (sz--) {
            ld x, y; cin >> x >> y;
            add(Point(x, y));
        }
    }

    void add(Point p) { poly.push_back(p); }
    void add(vector<Point> pp) { for (auto &p : pp) poly.push_back(p); }
    void set(vector<Point> pp) { poly = pp; }
    Point get(ll i) { return poly[i]; } // DANGER
    ll size() const { return poly.size(); }

    ld height() const { return (poly[0]-poly[1]).dist(); } // DANGER
    ld width() const { return (poly[1]-poly[2]).dist(); } // DANGER
    void shift(Point s) { for (auto &p : poly) p = p + s; }

    ld area() const {
        ld res = 0.0;
        int n = poly.size();

        for (int i = 0; i < n; i++) {
            int a = i, b = (i+1) % n;
            Point A = poly[a], B = poly[b];

            res += A.cross(B);
        }

        return abs(res / 2.0);
    }

    void clear() { id = -1, poly.clear(); }

    friend ostream& operator<<(ostream &os, Polygon poly) {
        int n = poly.size();
        os << n << " ";
        for (int i = 0; i < n; i++) {
            if (i) os << " ";
            os << poly.poly[i];
        }

        return os;
    }
};

int ID = 1;
vector<vector<Polygon>> construct, decomp;

void performCuts(const Polygon &poly, vector<Polygon> &pieces) {
    cout << "scissors" << endl;
    cout << poly.id << " " << pieces.size() << endl;
    // cerr << poly.id sp poly << endl;

    for (auto &piece : pieces) {
        piece.id = ID++;
        cout << piece << endl;
    }
}

void performPaste(Polygon &poly, vector<Polygon> &pieces) {
    cout << "tape" << endl;
    cout << pieces.size() << " ";

    for (auto &piece : pieces) {
        cout << piece.id << " ";
    }   cout << endl;

    for (auto &piece : pieces) {
        cout << piece << endl;
    }

    poly.id = ID++;
    cout << poly << endl;
}

// Check if P is in ABC
bool inTriangle(Point p, Point a, Point b, Point c) {
    ld area = abs(a.cross(b, c));
    ld a1 = abs(a.cross(b, p)), a2 = abs(b.cross(c, p)), a3 = abs(c.cross(a, p));
    return abs(area - (a1 + a2 + a3)) < EPS;
}

pair<Polygon, Polygon> decomposeTriangle(Polygon poly) {
    pair<Polygon, Polygon> res;

    int n = poly.size();
    for (int i = 0; i < n; i++) {
        int a = i, b = (i+1) % n, c = (i+2) % n;
        Point A = poly.get(a), B = poly.get(b), C = poly.get(c);

        if (A.cross(B, C) < 0) continue;

        bool convex = true;
        for (int j = 0; j < n; j++) {
            if (j == a or j == b or j == c) continue;
            if (inTriangle(poly.get(j), A, B, C)) {
                convex = false;
                break;
            }
        }

        if (!convex) continue;

        res.first.add({A, B, C});

        for (int j = 0; j < n; j++) {
            if (j == b) continue;
            res.second.add(poly.get(j));
        }

        return res;
    }

    assert(false);
    return res;
}

// Decompose a polygon into triangles
vector<Polygon> decomposeTriangles(Polygon poly, bool apply) {
    vector<Polygon> processed, unprocessed;

    unprocessed.push_back(poly);

    while (!unprocessed.empty()) {
        auto C = unprocessed.back(); unprocessed.pop_back();
        if (C.size() == 3) { processed.push_back(C); continue; }
        auto [A, B] = decomposeTriangle(C);

        A.size() > 3 ? unprocessed.push_back(A) : processed.push_back(A);
        B.size() > 3 ? unprocessed.push_back(B) : processed.push_back(B);
    }

    if (apply) performCuts(poly, processed);

    return processed;
}

// Compose rectangles from triangles (not optimal cut usage)
vector<Polygon> composeRectangles(vector<Polygon> &pieces, bool apply) {
    vector<Polygon> res;

    for (auto &piece : pieces) {
        Point A, B, C, D;

        int n = piece.size();
        assert(n == 3);

        // Find longest height to:
        // - guarantee altitude is inside the triangle
        // - splitting by the altitute results in two triangles
        for (int i = 0; i < n; i++) {
            int u = i, v = (i+1) % n, w = (i+2) % n;
            Point U = piece.get(u), V = piece.get(v), W = piece.get(w);
            if ((U-V).dist() > (A-B).dist()) { A = U, B = V, C = W; }
        }

        // Dear Prof. Schneider, I finally used something you taught me.
        // Project AC onto AB
        {
            Point u = B - A, v = C - A;
            D = A + (u * (v.dot(u) / u.dot(u)));
        }

        // 90-degree check
        assert((B-D).dot(C-D) < EPS);

        // Split into two right triangles
        vector<Polygon> right(2), cuts, pastes;
        Point E, F;

        right[0].add({A, D, C});
        right[1].add({C, D, B});

        if (apply) performCuts(piece, right);

        {
            // Split into a trapezoid and right triangle
            // Similar triangles
            Point M = (C+D) / 2;
            Point N = (A+C) / 2;

            vector<Polygon> split(2);

            split[0].add({A, D, M, N});
            split[1].add({N, M, C});

            if (apply) performCuts(right[0], split);
            else pastes.push_back(split[0]), pastes.push_back(split[1]);

            // Combine into a rectangle
            E = (A-D) + M;

            split[1].set({N, E, A});

            cuts.push_back(split[0]);
            cuts.push_back(split[1]);
        }

        {
            // Split into a trapezoid and right triangle
            // Similar triangles
            Point M = (C+D) / 2;
            Point N = (B+C) / 2;

            vector<Polygon> split(2);

            split[0].add({D, B, N, M});
            split[1].add({M, N, C});

            if (apply) performCuts(right[1], split);
            else pastes.push_back(split[0]), pastes.push_back(split[1]);

            // Combine into a rectangle
            F = (B-D) + M;

            split[1].set({F, N, B});

            cuts.push_back(split[0]);
            cuts.push_back(split[1]);
        }

        Polygon G;
        G.set({A, B, F, E});

        if (apply) performPaste(G, cuts);
        else construct.push_back(cuts), decomp.push_back(pastes);

        res.push_back(G);
    }

    return res;
}

vector<Polygon> normalizeRectangles(vector<Polygon> &pieces, vector<ld> &heights, bool apply) {
    vector<Polygon> res;

    assert(pieces.size() == heights.size());

    int n = pieces.size();
    for (int i = 0; i < n; i++) {
        Polygon piece = pieces[i];

        assert(piece.size() == 4);
        ld h = piece.height();

        // Two cases: smaller or larger

        if (h > heights[i]) {
            while (h > 2 * heights[i]) {
                Point A, B, C, D, E, F, G, H, S;
                A = piece.get(0);
                B = piece.get(1);
                C = piece.get(2);
                D = piece.get(3);
                S = D - A;
                E = (A + B) / 2;
                F = E + S;
                G = F + S;
                H = D + S;

                vector<Polygon> split(2);
                split[0].set({A, E, F, D});
                split[1].set({E, B, C, F});
                performCuts(piece, split);

                piece.set({A, E, G, H});
                split[1].set({D, F, G, H});
                performPaste(piece, split);

                h = piece.height();
            }
        }
        
        else {
            while (h < heights[i]) {
                Point A, B, C, D, E, F, G, H, S;
                A = piece.get(0);
                B = piece.get(1);
                C = piece.get(2);
                D = piece.get(3);
                S = B - A;
                E = (A + D) / 2;
                F = E + S;
                G = F + S;
                H = B + S;

                vector<Polygon> split(2);
                split[0].set({A, B, F, E});
                split[1].set({E, F, C, D});
                performCuts(piece, split);

                piece.set({A, H, G, E});
                split[1].set({B, H, G, F});
                performPaste(piece, split);

                h = piece.height();
            }
        }

        // We now cannot perform more mul/div by 2 operations
        // Shift by dh in at most 2 cuts
        ld dh = h - heights[i];
        Point A, B, C, D, E, F, G, H, S, T;
        A = piece.get(0);
        B = piece.get(1);
        C = piece.get(2);
        D = piece.get(3);
        S = (B - A).unit() * dh;
        E = A + S;
        F = C - S;
        G = B - S;
        ld pr = (E - A).dist() / (G - A).dist();
        T = (F - A).unit() * (F - A).dist() * pr;
        H = A + T;

        vector<Polygon> split(3);
        split[0].set({E, B, C, F, H});
        split[1].set({A, F, D});
        split[2].set({A, E, H});

        performCuts(piece, split);

        // Let D be stationary
        Point nA, nB, nC, Q;
        ld dw = (H - E).dist();
        Q = (A - D).unit() * dw;
        split[0].shift(Q - S);
        split[2].set({F+Q-S, C+Q-S, F});

        piece.set({A+Q, G+Q, F, D});

        performPaste(piece, split);

        res.push_back(piece);
    }

    return res;
}

Polygon combineRectangle(vector<Polygon> &pieces, ld height) {
    // Stack all pieces together
    Polygon res;
    ld width = 0;

    for (auto &piece : pieces) {
        ld w = piece.width();

        Point A(0, height), B(0, 0), C(w, 0), D(w, height), S(width, 0);
        piece.set({A+S, B+S, C+S, D+S});

        width += w;
    }

    Point A(0, height), B(0, 0), C(width, 0), D(width, height);
    res.set({A, B, C, D});

    performPaste(res, pieces);

    return res;
}

vector<Polygon> separateRectangle(Polygon rect, vector<Polygon> &pieces, ld height) {
    vector<Polygon> res;

    for (auto &piece : pieces) {
        ld area = piece.area();
        ld width = area / height;

        if (abs(rect.width() - width) < EPS) {
            res.push_back(rect);
            continue;
        }

        Point A, B, C, D, E, F, S;
        A = rect.get(0);
        B = rect.get(1);
        C = rect.get(2);
        D = rect.get(3);
        E = D - width;
        F = C - width;

        vector<Polygon> split(2);
        split[0].set({A, B, F, E});
        split[1].set({E, F, C, D});
        
        performCuts(rect, split);

        rect = split[0];
        res.push_back(split[1]);

        assert(abs(split[1].area() - area) < EPS);
    }

    return res;
}

pair<Point, ld> findTransformation(const Polygon &source, const Polygon &target) {
    assert(source.size() == target.size());
    
    Point s1 = source.poly[0], s2 = source.poly[1];
    Point t1 = target.poly[0], t2 = target.poly[1];
    
    Point translation = t1 - s1;
    
    Point sv = s2 - s1;
    Point tv = t2 - t1;
    ld angle = tv.angle() - sv.angle();
    
    return {translation, angle};
}

Point transformPoint(const Point &p, const Point &center, const Point &translation, ld angle) {
    Point translated = p - center;
    Point rotated = translated.rotate(angle);
    return rotated + center + translation;
}

vector<Polygon> composeTriangles(vector<Polygon> &pieces, vector<Polygon> &blueprint, vector<Polygon> &target) {
    vector<Polygon> res;

    assert(pieces.size() == blueprint.size());
    assert(pieces.size() == construct.size());
    assert(pieces.size() == decomp.size());

    int n = pieces.size();
    for (int i = 0; i < n; i++) {
        auto &piece = pieces[i];
        auto &blue = blueprint[i];
        
        auto [translation, angle] = findTransformation(blue, piece);
        Point center = blue.poly[0];
        
        vector<Polygon> relayed;
        for (auto &rpol : construct[i]) {
            Polygon transformed;
            transformed.id = rpol.id;
            
            for (int j = 0; j < rpol.size(); j++) {
                Point P = rpol.get(j);
                Point Q = transformPoint(P, center, translation, angle);
                transformed.add(Q);
            }
            
            relayed.push_back(transformed);
        }

        performCuts(piece, relayed);

        for (int j = 0; j < 4; j++) {
            decomp[i][j].id = relayed[j].id;
        }
        
        performPaste(target[i], decomp[i]);

        res.push_back(target[i]);
    }

    return res;
}

void solve() {
    Polygon S(0), T;
    int s; cin >> s; S.input(s);
    int t; cin >> t; T.input(t);

    ld h = sqrtl(T.area());

    vector<Polygon> U1 = decomposeTriangles(S, true);
    vector<Polygon> U2 = composeRectangles(U1, true);
    vector<ld> H1(U2.size(), h);
    vector<Polygon> U3 = normalizeRectangles(U2, H1, true);
    Polygon U4 = combineRectangle(U3, h);

    vector<Polygon> V1 = decomposeTriangles(T, false);
    vector<Polygon> V2 = composeRectangles(V1, false);
    vector<Polygon> V3 = separateRectangle(U4, V2, h);
    vector<ld> H2; for (auto &poly : V2) H2.push_back(poly.height());
    vector<Polygon> V4 = normalizeRectangles(V3, H2, true); 
    vector<Polygon> V5 = composeTriangles(V4, V2, V1);

    performPaste(T, V5);
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cout << fixed << setprecision(12);
    // cerr << fixed << setprecision(3);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 10 / 10
• Subtask 6: 16 / 16
• Subtask 7: 11 / 11
• Subtask 8: 19 / 19