Submission #1229331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229331		ProtonDecay314	Scissors and Tape (CEOI19_scissors)	C++20	30 / 100	3 ms	584 KiB

scissors

/*
polygon
-> triangles
    -> axis-aligned triangle with "center" at (0, 0) [align_triangle]
    -> triangle fragments aligned with triangle [cross_decompose::first]
    -> triangle fragments aligned with rectangle [cross_decompose::second]
    -> axis-aligned rectangle with one vertex at (0, 0) [unnorm_rectangle]
    -> normalized rectangle [bisect_rect, double_rect, slice_unnorm_rect, normalize_rect] TODO
    -> normalized rectangle with correct position [translate_polygon] TODO
-> giga normalized rectangle

Representation:

graph, each node stores its outgoing and incoming connections
struct shape {
    polygon p;
    int id = -1; // initially -1 (unprocessed)
    vector<shape*> from, to;
}

tapos to reverse the graph, you just swap the from and to vectors for everything

finally, do a dfs to determine the IDs, tapos compile all the shapes into a large vector

process everything in the vector in order
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<double> vd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

const double EPS = 0.000001;

struct vec2d {
    double x, y;

    const vec2d operator+(const vec2d& o) const {
        return {x + o.x, y + o.y};
    }

    const vec2d operator-(const vec2d& o) const {
        return {x - o.x, y - o.y};
    }
};

typedef vector<vec2d> polygon;

void printpoly(const polygon& p) {
    int n = p.size();

    cout << n;

    for(int i = 0; i < n; i++) {
        cout << setprecision(15) << " " << p[i].x << " " << p[i].y;
    }

    cout << "\n";
}

void printpoly_cerr(const polygon& p) {
    for(auto [x, y] : p) {
        cerr << " { " << x << ", " << y << " }, ";
    }
    cerr << endl;
}

polygon translate_polygon(const polygon& p, const vec2d& tr) {
    int n = p.size();

    polygon res = p;

    for(int i = 0; i < n; i++) {
        res[i] = res[i] + tr;
    }

    return res;
}

inline polygon create_rect(double x, double y, double w, double h) {
    return {{x, y}, {x + w, y}, {x + w, y + h}, {x, y + h}};
}

/*
computational_node handler
*/
// int cur_id = 0;

struct cnode {
    polygon p;
    int id = -1; // initially -1 (unprocessed)
    vector<cnode*> from, to;
    bool vis;

    cnode(const polygon& a_p, const vector<cnode*>& a_from, bool reversed): p(a_p), id(-1), from(), to(), vis(false) {
        if(reversed) {
            to = a_from;
            
            int n = to.size();

            /*
            push the current cnode to the "from" field of each next cnode
            */
            for(int i = 0; i < n; i++) {
                to[i]->from.pb(this);
            }
        } else {
            from = a_from;
            
            int n = from.size();

            /*
            push the current cnode to the "to" field of each previous cnode
            */
            for(int i = 0; i < n; i++) {
                from[i]->to.pb(this);
            }
        }
    }
};

void cnode_link(cnode* from, cnode* to) {
    from->to.pb(to);
    to->from.pb(from);
}

vector<cnode*> cnode_decompose(const vector<polygon>& res_poly, cnode* source_cnode, bool rev) {
    int n = res_poly.size();

    vector<cnode*> res(n, nullptr);

    for(int i = 0; i < n; i++) {
        res[i] = new cnode(res_poly[i], {source_cnode}, rev);
    }

    return res;
}

/*
gets euclidean distance between two points
*/
double dist(const vec2d& a, const vec2d& b) {
    double diffy = a.y - b.y, diffx = a.x - b.x;
    return sqrt(diffy * diffy + diffx * diffx);
}

/*
uses right-hand rule convention (out of the page is positive)
*/
double cross2d(const vec2d& a, const vec2d& b) {
    return a.x * b.y - a.y * b.x;
}

bool is_ccw(const vec2d& p1, const vec2d& p2, const vec2d& p3) {
    vec2d diff1 = p1 - p2, diff2 = p3 - p2;

    return cross2d(diff1, diff2) < 0.0;
}

/*
convention: ccw = positive
*/
double signed_area(const polygon& p) {
    double twice_area = 0.0;

    int n = p.size();

    for(int i = 0; i < n; i++) {
        int i2 = (i + 1) % n;

        twice_area += p[i2].y * p[i].x - p[i2].x * p[i].y;
    }

    return twice_area * 0.5;
}

bool is_inside(const polygon& tri, const vec2d& t) {
    return is_ccw(t, tri[0], tri[1]) && is_ccw(t, tri[1], tri[2]) && is_ccw(t, tri[2], tri[0]);
}

vector<polygon> triangulate(const polygon& p) {
    int n = p.size();

    // Base case: already a triangle
    if(n == 3) return {p};

    // Recursive case: for each pivot, check if it forms a ccw set with no other points inside

    polygon new_tri;

    int chosen_ind = -1;

    for(int i = 0; i < n; i++) {
        int previ = (i + n - 1) % n;
        int nexti = (i + 1) % n;
        vec2d pivot = p[i];
        vec2d prevp = p[previ];
        vec2d nextp = p[nexti];
        polygon cur_tri = {prevp, pivot, nextp};

        if(!is_ccw(prevp, pivot, nextp)) continue;

        int num_points_inside = 0;

        for(int j = 0; j < n; j++) {
            if(j == i || j == previ || j == nexti) continue;

            if(is_inside(cur_tri, p[j])) num_points_inside++;
        }

        if(num_points_inside > 0) continue;

        new_tri = cur_tri;

        chosen_ind = i;

        break;
    }

    polygon new_p;

    for(int i = 0; i < n; i++) {
        if(i == chosen_ind) continue;
        new_p.pb(p[i]);
    }

    vector<polygon> recurs = triangulate(new_p);

    recurs.pb(new_tri);

    return recurs;
}

/*
Computing triangle invariants
*/
struct triangle_invariant {
    double a, b, c, A, h, m, n;
};

triangle_invariant compute_tri_invariants(const polygon& tri) {
    double a = dist(tri[1], tri[2]), b = dist(tri[2], tri[0]), c = dist(tri[0], tri[1]);

    double A = signed_area(tri);

    assert(A >= 0.0);

    double h = 2.0 * A / b;

    double m = sqrt(a * a - h * h), n = sqrt(c * c - h * h);

    return {a, b, c, A, h, m, n};
}


/*
Aligns a triangle with the origin
*/
polygon align_triangle(const polygon& tri) {
    auto [a, b, c, A, h, m, n] = compute_tri_invariants(tri);

    return {
        {n, -h * 0.5}, {0.0, h * 0.5}, {-m, -h * 0.5}
    };
}

/*
Decomposes a triangle into four parts, which can be reassembled into a rectangle

first entry: origin-triangle-aligned
second entry: rectangle-aligned 
*/
pair<vector<polygon>, vector<polygon>> cross_decompose(const polygon& tri) {
    auto [a, b, c, A, h, m, n] = compute_tri_invariants(tri);

    // ! TODO return both the coordinates within the triangle and the translated coordinates
    return {
        {
            {{0.0, 0.0}, {0.0, h * 0.5}, {-m * 0.5, 0.0}}, /* top-left */
            {{0.0, 0.0}, {n * 0.5, 0.0}, {0.0, h * 0.5}}, /* top-right */
            {{0.0, 0.0}, {-m * 0.5, 0.0}, {-m, -h * 0.5}, {0.0, -h * 0.5}}, /* bottom-left */
            {{0.0, 0.0}, {0.0, -h * 0.5}, {n, -h * 0.5}, {n * 0.5, 0.0}} /* bottom-right */
        },
        {
            {{0.0, h * 0.5}, {0.0, 0.0}, {m * 0.5, h * 0.5}}, /* top-left */
            {{b, h * 0.5}, {b - n * 0.5, h * 0.5}, {b, 0.0}}, /* top-right */
            {{m, h * 0.5}, {m * 0.5, h * 0.5}, {0.0, 0.0}, {m, 0.0}}, /* bottom-left */
            {{m, h * 0.5}, {m, 0.0}, {b, 0.0}, {b - n * 0.5, h * 0.5}} /* bottom-right */
        }
    };
}

/*
returns the resultant rectangle from a triangle

CONVENTION FOR RECTANGLES: start from bottom-left
*/
polygon unnorm_rectangle(const polygon& tri) {
    auto [a, b, c, A, h, m, n] = compute_tri_invariants(tri);

    return {
        {0.0, 0.0},
        {b, 0.0},
        {b, h * 0.5},
        {0.0, h * 0.5}
    };
}

inline double rect_height(const polygon& rect) {
    return rect[2].y - rect[0].y;
}

inline double rect_width(const polygon& rect) {
    return rect[2].x - rect[0].x;
}

/*
cuts a rectangle into two, doubling the height

first: unnorm_rectangle-aligned
second: doubled_rectangle-aligned
*/
pair<vector<polygon>, vector<polygon>> bisect_rect_double_height(const polygon& rect) {
    auto [w, h] = rect[2];

    return {
        {
            {{0.0, 0.0}, {w * 0.5, 0.0}, {w * 0.5, h}, {0.0, h}},
            {{w * 0.5, 0.0}, {w, 0.0}, {w, h}, {w * 0.5, h}}
        },
        {
            {{0.0, 0.0}, {w * 0.5, 0.0}, {w * 0.5, h}, {0.0, h}},
            {{0.0, h}, {w * 0.5, h}, {w * 0.5, 2.0 * h}, {0.0, 2.0 * h}}
        }
    };
}

/*
halves the width, doubles the height

NOTE: double the height until it is STRICTLY greater than 10^6

might want to actually set a larger threshold just so that you don't run into weird epsilon-sized polygons
*/
polygon double_rect(const polygon& rect) {
    auto [w, h] = rect[2];

    return {{0.0, 0.0}, {w * 0.5, 0.0}, {w * 0.5, h * 2.0}, {0.0, h * 2.0}};
}

/*
cuts a rectangle into two, halving the height

first: unnorm_rectangle-aligned
second: doubled_rectangle-aligned
! NOTE no need for this pala WHAHAHA the constraints guarantee that this does not need to be done
*/
// pair<vector<polygon>, vector<polygon>> bisect_rect_halve_height(const polygon& rect) {
//     auto [w, h] = rect[2];

//     return {
//         {
//             {{0.0, 0.0}, {w, 0.0}, {w, h * 0.5}, {0.0, h * 0.5}},
//             {{0.0, h * 0.5}, {w, h * 0.5}, {w, h}, {0.0, h}}
//         },
//         {
//             {{0.0, 0.0}, {w, 0.0}, {w, h * 0.5}, {0.0, h * 0.5}},
//             {{w, 0.0}, {2.0 * w, 0.0}, {2.0 * w, h * 0.5}, {w, h * 0.5}}
//         }
//     };
// }

/*
fixed constant to normalize rectangle heights to
*/
const double NORM_HEIGHT = 1000000.0;

/*
slices an unnormalized rectangle into pieces that can be rearranged into a normalized rectangle

first: pieces aligned with the unnormalized rectangle
second pieces aligned with the normalized rectangle
*/
pair<vector<polygon>, vector<polygon>> slice_unnorm_rect(const polygon& rect) {
    auto [w, h] = rect[2];

    double corr_term = w * (h / NORM_HEIGHT - 1.0);
    double excess_h = h - NORM_HEIGHT;

    return {
        {
            {{0.0, 0.0}, {w, 0.0}, {w, NORM_HEIGHT}, {w - corr_term, NORM_HEIGHT}, {0.0, excess_h}}, /*pentagon*/
            {{w - corr_term, NORM_HEIGHT}, {w, NORM_HEIGHT}, {w, h}}, /*small triangle*/
            {{0.0, excess_h}, {w, h}, {0.0, h}} /*big triangle*/
        },
        {
            {{corr_term, 0.0}, {w * h / NORM_HEIGHT, 0.0}, {w * h / NORM_HEIGHT, NORM_HEIGHT}, {w, NORM_HEIGHT}, {corr_term, excess_h}}, /*pentagon*/
            {{0.0, 0.0}, {corr_term, 0.0}, {corr_term, excess_h}}, /*small triangle*/
            {{0.0, 0.0}, {w, NORM_HEIGHT}, {0.0, NORM_HEIGHT}} /*big triangle*/
        }
    };
}

/*
normalizes a rectangle to have a fixed height
*/
polygon normalize_rect(const polygon& rect) {
    auto [w, h] = rect[2];

    double new_w = w * h / NORM_HEIGHT;

    return create_rect(0.0, 0.0, new_w, NORM_HEIGHT);
}

/*
constructs a "forward pass" that reduces any polygon down to a normalized rectangle

note that this normalized rectangle is invariant;
two shapes are equidecomposable if and only if they have the same normalized rectangle invariant
first: the starting cnode
second: the ending cnode
*/
pair<cnode*, cnode*> forward_pass(const polygon& inp, bool rev) {
    /*
    polygon
    -> triangles
        -> axis-aligned triangle with "center" at (0, 0) [align_triangle]
        -> triangle fragments aligned with triangle [cross_decompose::first]
        -> triangle fragments aligned with rectangle [cross_decompose::second]
        -> axis-aligned rectangle with one vertex at (0, 0) [unnorm_rectangle]
        -> normalized rectangle [bisect_rect, double_rect, slice_unnorm_rect, normalize_rect]
        -> normalized rectangle with correct position [translate_polygon]
    -> giga normalized rectangle
    */
    
    cnode* start = new cnode(inp, {}, rev);

    // 1. triangulating
    vector<polygon> triangles = triangulate(inp);
    vector<cnode*> triangle_cnodes = cnode_decompose(triangles, start, rev);

    int ntri = triangles.size();
    
    vector<cnode*> special_rects(ntri, nullptr);
    
    
    for(int i = 0; i < ntri; i++) {
        // 2. axis-aligning
        cnode* axis_aligned_tri = new cnode(align_triangle(triangle_cnodes[i]->p), {triangle_cnodes[i]}, rev);
        
        // 3. converting to rectangle
        auto [axis_aligned_decomp, rect_aligned_decomp] = cross_decompose(axis_aligned_tri->p);
        
        vector<cnode*> axis_aligned_decomp_res = cnode_decompose(axis_aligned_decomp, axis_aligned_tri, rev);
        vector<cnode*> rect_aligned_decomp_res(4, nullptr);
        
        for(int j = 0; j < 4; j++) {
            rect_aligned_decomp_res[j] = new cnode(rect_aligned_decomp[j], {axis_aligned_decomp_res[j]}, rev);
        }
        
        cnode* unnormed_unscaled_rect = new cnode(unnorm_rectangle(axis_aligned_tri->p), rect_aligned_decomp_res, rev);
        
        // 4. rescaling the rectangle
        cnode* scaled_rect = unnormed_unscaled_rect;
        
        while(rect_height(scaled_rect->p) < NORM_HEIGHT) {
            auto [bisect_align_initial, bisect_align_final] = bisect_rect_double_height(scaled_rect->p);
            
            polygon resultant_rect = double_rect(scaled_rect->p);
            
            vector<cnode*> bisect_res = cnode_decompose(bisect_align_initial, scaled_rect, rev);
            vector<cnode*> aligned_with_final(2, nullptr);

            for(int j = 0; j < 2; j++) {
                aligned_with_final[j] = new cnode(bisect_align_final[j], {bisect_res[j]}, rev);
            }

            scaled_rect = new cnode(resultant_rect, aligned_with_final, rev);
        }

        cnode* special_rect = nullptr;

        if(abs(rect_height(scaled_rect->p) - NORM_HEIGHT) > EPS) {
            // 5. Turning into a special rectangle
            auto [unnormed_align, normed_align] = slice_unnorm_rect(scaled_rect->p);
            
            vector<cnode*> unnormed_aligned_cnodes = cnode_decompose(unnormed_align, scaled_rect, rev);
            vector<cnode*> normed_aligned_cnodes(3, nullptr);

            for(int j = 0; j < 3; j++) {
                normed_aligned_cnodes[j] = new cnode(normed_align[j], {unnormed_aligned_cnodes[j]}, rev);
            }

            special_rect = new cnode(normalize_rect(scaled_rect->p), normed_aligned_cnodes, rev);
        } else {
            // it's already a special rectangle; do nothing
            special_rect = scaled_rect;
        }

        special_rects[i] = special_rect;
    }

    // 6. combine all special rectangles into one
    double tot_w = 0.0;

    for(int i = 0; i < ntri; i++) {
        tot_w += rect_width(special_rects[i]->p);
    }

    polygon final_rect = create_rect(0.0, 0.0, tot_w, NORM_HEIGHT);
    
    
    vector<cnode*> aligned_special_rects(ntri, nullptr);

    double cur_left_x = 0.0;
    for(int i = 0; i < ntri; i++) {
        auto [w, h] = special_rects[i]->p[2];
        aligned_special_rects[i] = new cnode(create_rect(cur_left_x, 0.0, w, h), {special_rects[i]}, rev);

        cur_left_x += w;
    }

    cnode* end = new cnode(final_rect, aligned_special_rects, rev);

    if(rev) return {end, start};
    return {start, end};
}

/*
constructs a full "computational graph" that converts from one rectangle to another

first: start
second: end
*/
pair<cnode*, cnode*> full_compgraph(const polygon& s, const polygon& e) {
    auto [start, rect_1] = forward_pass(s, false);
    auto [rect_2, end] = forward_pass(e, true);

    cnode_link(rect_1, rect_2);

    return {start, end};
}

/*
assigns IDs to nodes in the computational graph according to BFS order starting from shape 0;
returns the list of IDs in increasing order
*/
vector<cnode*> all_nodes(cnode* s) {
    queue<cnode*> q;

    q.push(s);

    vector<cnode*> res;

    int cur_id = 0;

    while(!q.empty()) {
        cnode* cur = q.front();

        q.pop();

        if(cur->vis) continue;

        cur->vis = true;
        res.pb(cur);

        cur->id = cur_id++;

        for(cnode* j : cur->to) {
            q.push(j);
        }
    }

    int n = res.size();

    for(int i = 0; i < n; i++) res[i]->vis = false;

    return res;
}

/*
prints the sequence of operations based on the BFS ordering

note: if there is exactly one incoming edge, and the node on the other side of this edge has exactly one outgoing edge,
we can perform "tape"
if there are multiple incoming edges, we are forced to tape
if there are multiple outgoing edges, we are forced to scissor 

just go through these conditions in order and eagerly perform operations as needed
*/
void print_ops(vector<cnode*>& nodes) {
    int n = nodes.size();
    
    int cur_id = 0;


    while(true) {
        // finding an unprocessed node
        int node_ind = -1;

        for(int i = 0; i < n; i++) {
            if(nodes[i]->vis) continue;
            bool possible = true;

            for(cnode* prereq : nodes[i]->from) {
                if(!prereq->vis) {
                    possible = false;
                    break;
                }
            }

            if(possible) {
                node_ind = i;
                break;
            }
        }

        if(node_ind == -1) break;

        cnode* cur = nodes[node_ind];

        /*
        if there is exactly one incoming edge, and the node on the other side of this edge has exactly one outgoing edge,
        we can perform "tape"
        if there are multiple incoming edges, we are forced to tape
        if there are multiple outgoing edges, we are forced to scissor
        */
        if((int)(cur->from.size()) == 0) {
            // initialize start
            cur->id = cur_id++;
        } else if((int)(cur->from.size()) == 1 && (int)(cur->from[0]->to.size()) == 1) {
            // perform tape
            cur->id = cur_id++;

            cout << "tape" << "\n";

            cout << "1 " << cur->from[0]->id << "\n";
            
            for(int i = 0; i < 2; i++) printpoly(cur->p);

        } else if((int)(cur->from.size()) > 1) {
            // perform tape
            cur->id = cur_id++;

            int k = cur->from.size();

            cout << "tape" << "\n";
            cout << k;

            for(int i = 0; i < k; i++) {
                cout << " " << cur->from[i]->id;
            }
            cout << "\n";

            for(int i = 0; i < k; i++) {
                printpoly(cur->from[i]->p);
            }

            printpoly(cur->p);
        }
        
        if((int)(cur->to.size()) > 1) {
            // perform scissor
            cout << "scissors" << "\n";

            cout << cur->id << " " << cur->to.size() << "\n";

            for(cnode* decomp_res : cur->to) {
                printpoly(decomp_res->p);
                decomp_res->id = cur_id++;
            }
        }

        // marking as visited
        cur->vis = true;
    }
}

/*
inputs a polygon
*/
polygon inp_poly() {
    int n;
    cin >> n;

    polygon res;

    for(int i = 0; i < n; i++) {
        double x, y;
        cin >> x >> y;

        res.pb({x, y});
    }

    return res;
}

/*
NOTE: the computational graph will include redundant ops where i just reposition some of the stuff
that will ensure that every time i glue things together, i can just reuse the coordinates of the shapes
when gluing
*/

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

    
    polygon s = inp_poly(), e = inp_poly();
    
    auto [sn, en] = full_compgraph(s, e);

    vector<cnode*> nodes = all_nodes(sn);

    print_ops(nodes);

    return 0;
}

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