Submission #1229427

#TimeUsernameProblemLanguageResultExecution timeMemory
1229427ProtonDecay314Scissors and Tape (CEOI19_scissors)C++20
30 / 100
3 ms584 KiB
/* 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; #define double long double 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}; } const vec2d operator*(double o) const { return {x * o, y * o}; } double length() { return sqrt(x * x + y * y); } double norm() { return x * x + y * 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(18) << " " << 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; } double dot2d(const vec2d& a, const vec2d& b) { return a.x * b.x + a.y * b.y; } bool is_nonobtuse(const vec2d& p1, const vec2d& pivot, const vec2d& p2) { vec2d d1 = p1 - pivot, d2 = p2 - pivot; return dot2d(d1, d2) >= 0.0; } bool is_nonobtuse_tri(const polygon& p) { return is_nonobtuse(p[0], p[1], p[2]) && is_nonobtuse(p[1], p[2], p[0]) && is_nonobtuse(p[2], p[0], p[1]); } 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); if(is_nonobtuse_tri(new_tri)) { recurs.pb(new_tri); } else { cerr << "hitotsu ni naru" << endl; for(int i = 0; i < 3; i++) { int pi = (i + 2) % 3, ni = (i + 1) % 3; if(!is_nonobtuse(new_tri[pi], new_tri[i], new_tri[ni])) { // subdivide into two vec2d d1 = new_tri[ni] - new_tri[pi], d2 = new_tri[i] - new_tri[pi]; vec2d newp = new_tri[pi] + (d1 * (dot2d(d1, d2) / (d1.norm()))); polygon tri1 = {new_tri[pi], new_tri[i], newp}, tri2 = {new_tri[i], new_tri[ni], newp}; // printpoly_cerr(tri1); // printpoly_cerr(tri2); // if(signed_area(tri1) <= 0.0) { // printpoly_cerr(tri1); // assert(false); // } // if(signed_area(tri2) <= 0.0) { // printpoly_cerr(tri2); // assert(false); // } recurs.pb(tri1); recurs.pb(tri2); break; } } } 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); // if(A < 0.0) { // cerr << A << endl; // assert(false); // } 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); // assert areas are equal if(abs(signed_area(cur->p) - signed_area(cur->from[0]->p)) > 0.001) { cerr << "FAILED: " << signed_area(cur->p) << " " << signed_area(cur->from[0]->p) << endl; printpoly_cerr(cur->from[0]->p); printpoly_cerr(cur->p); // assert(false); } } else if((int)(cur->from.size()) > 1) { // perform tape cur->id = cur_id++; int k = cur->from.size(); cout << "tape" << "\n"; cout << k; double tot_area = 0.0; for(int i = 0; i < k; i++) { cout << " " << cur->from[i]->id; tot_area += signed_area(cur->from[i]->p); } cout << "\n"; for(int i = 0; i < k; i++) { printpoly(cur->from[i]->p); } printpoly(cur->p); // assert areas are equal double final_area = signed_area(cur->p); if(abs(tot_area - final_area) >= 0.001) { cerr << "FAILED: " << tot_area << " " << final_area << endl; // assert(false); } } if((int)(cur->to.size()) > 1) { // perform scissor cout << "scissors" << "\n"; cout << cur->id << " " << cur->to.size() << "\n"; double tot_area = 0.0; for(cnode* decomp_res : cur->to) { printpoly(decomp_res->p); decomp_res->id = cur_id++; tot_area += signed_area(decomp_res->p); } // checking areas double undecomp_area = signed_area(cur->p); if(abs(tot_area - undecomp_area) >= 0.001) { cerr << "FAILED: " << tot_area << " " << undecomp_area << endl; // assert(false); } } // 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); // printpoly_cerr(align_triangle({{0.0, 9.0}, {6.0, 0.0}, {5.0, 4.0}})); // cerr << signed_area({{0.0, 9.0}, {6.0, 0.0}, {5.0, 4.0}}) << endl; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...