Submission #198124

#	Time	Username	Problem	Language	Result	Execution time	Memory
198124		model_code	Scissors and Tape (CEOI19_scissors)	C++17	100 / 100	13 ms	448 KiB

scissors

#include <algorithm>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

// universal geometric functions

typedef double rational;
typedef complex<rational> point;
typedef vector<point> poly;

const rational EPSILON = 1e-9;

bool is_negative(rational x) { return x < -EPSILON; }
bool is_zero(rational x) { return abs(x) <= EPSILON; }
bool is_positive(rational x) { return x > EPSILON; }
bool are_equal(rational x, rational y) { 
    if (is_zero(x-y)) return true;
    rational lo = min( x*(1-EPSILON), x*(1+EPSILON) ), hi = max( x*(1-EPSILON), x*(1+EPSILON) );
    return (lo <= y && y <= hi);
}
bool are_equal(const vector<rational> &A, const vector<rational> &B) {
    if (A.size() != B.size()) return false;
    for (unsigned n=0; n<A.size(); ++n) if (!are_equal(A[n],B[n])) return false;
    return true;
}
bool are_equal(const point &A, const point &B) { return is_zero(real(B)-real(A)) && is_zero(imag(B)-imag(A)); }
int signum(rational x) { if (is_zero(x)) return 0; if (is_negative(x)) return -1; return 1; }
rational square_size  (const point &A)                 { return real(A) * real(A) + imag(A) * imag(A); }
rational dot_product  (const point &A, const point &B) { return real(A) * real(B) + imag(A) * imag(B); }
rational cross_product(const point &A, const point &B) { return real(A) * imag(B) - real(B) * imag(A); }
rational size(const point &A) { return sqrt(real(A) * real(A) + imag(A) * imag(A)); }
void normalize(point &A) { rational Asize = size(A); A *= (1/Asize); }
bool colinear(const point &A, const point &B, const point &C) { return is_zero( cross_product( B-A, C-A )); }
bool colinear(const point &B, const point &C)                 { return is_zero( cross_product( B,   C ));   }
bool clockwise(const point &A, const point &B, const point &C) { return is_negative( cross_product( B-A, C-A )); }
bool clockwise(const point &B, const point &C)                 { return is_negative( cross_product( B,   C ));   }
bool counterclockwise(const point &A, const point &B, const point &C) { return is_positive( cross_product( B-A, C-A )); }
bool counterclockwise(const point &B, const point &C)                 { return is_positive( cross_product( B,   C ));   }

rational poly_area(const poly &V) { 
    rational res = 0;
    for (unsigned i=0; i<V.size(); i++) res += cross_product( V[i], V[(i+1)%V.size()] ); 
    return abs(0.5 * res);
}

vector<rational> side_lengths(const poly &P) {
    int N = P.size();
    vector<rational> answer;
    for (int n=0; n<N; ++n) answer.push_back( size( P[(n+1)%N] - P[n] ) );
    return answer;
}

// task-specific functions

int NEXT_ID;

struct object {
    int ID;
    poly P;
    object(const poly &P) : P(P) { ID = NEXT_ID++; }
};

void initialize() {
    NEXT_ID = 0;
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
}

void print_poly(const poly &P) { 
    cout << P.size(); 
    for (auto pt : P) cout << " " << real(pt) << " " << imag(pt);
    cout << endl;
}

poly load_poly() {
    int N; cin >> N;
    poly P(N);
    rational x, y;
    for (int n=0; n<N; ++n) { cin >> x >> y; P[n] = point(x,y); }
    return P;
}

poly nice_rectangle(rational x, rational y, rational dx = 0, rational dy = 0) { return { point(dx,dy), point(dx+x,dy), point(dx+x,dy+y), point(dx,dy+y) }; }

void cut_and_paste(int startWith, const vector<poly> &cutInto, const vector<poly> &rearrangeInto, const poly &endWith) {
    cout << "scissors" << endl << startWith << " " << cutInto.size() << endl;
    vector<int> new_ids;
    for (const auto &piece : cutInto) { new_ids.push_back( NEXT_ID++ ); print_poly(piece); }
    cout << "tape" << endl << rearrangeInto.size();
    for (int x : new_ids) cout << " " << x;
    cout << endl;
    for (const auto &piece : rearrangeInto) print_poly(piece);
    print_poly(endWith);
}

object nice_rectangle_to_nice_rectangle(object Rin, const poly &Rout) {
    while (true) {
        rational x1 = real(Rin.P[2]), y1 = imag(Rin.P[2]), x2 = real(Rout[2]), y2 = imag(Rout[2]);
        
        if (are_equal(x1,x2)) return Rin;

        if (!is_negative(x1 - 2*x2)) { // x1 is at least twice as big, fold in half
            cut_and_paste( 
                    Rin.ID, 
                    { nice_rectangle( x1/2, y1 ), nice_rectangle( x1/2, y1, x1/2,  0 ) },
                    { nice_rectangle( x1/2, y1 ), nice_rectangle( x1/2, y1,    0, y1 ) },
                    nice_rectangle( x1/2,y1*2 )
            );
            Rin = object(nice_rectangle(x1/2,y1*2));
            continue;
        }

        if (!is_negative(y1 - 2*y2)) { // y1 is at least twice as big, fold in half
            cut_and_paste(
                    Rin.ID, 
                    { nice_rectangle( x1, y1/2 ), nice_rectangle( x1, y1/2,  0, y1/2 ) },
                    { nice_rectangle( x1, y1/2 ), nice_rectangle( x1, y1/2, x1,    0 ) },
                    nice_rectangle( x1*2,y1/2 )
            );
            Rin = object(nice_rectangle(x1*2,y1/2));
            continue;
        }

        if (is_positive(x1 - x2)) { // x1 is at most twice as big, cut into three and reassemble
            rational offx = x1 - x2, offy = y1 * offx / x2;
            cut_and_paste(
                    Rin.ID,
                    { { point(0,0), point(x2,y1), point(0,y1) },    { point(0,0), point(offx,0), point(offx,offy) },   { point(offx,0), point(x1,0), point(x1,y1), point(x2,y1), point(offx,offy) } },
                    { { point(0,offy), point(x2,y2), point(0,y2) }, { point(x2-offx,y1), point(x2,y1), point(x2,y2) }, { point(0,0), point(x2,0), point(x2,y1), point(x2-offx,y1), point(0,offy) }  },
                    nice_rectangle(x2,y2)
            );
            return object(Rout);
        } else { // y1 is at most twice as big, cut into three and reassemble
            rational offy = y1 - y2, offx = x1 * offy / y2;
            cut_and_paste(
                    Rin.ID,
                    { { point(0,0), point(x1,0), point(x1,y2) },    { point(0,0), point(offx,offy), point(0,offy) },             { point(0,offy), point(offx,offy), point(x1,y2), point(x1,y1), point(0,y1) } },
                    { { point(offx,0), point(x2,0), point(x2,y2) }, { point(x2-offx,y2-offy), point(x2,y2), point(x2-offx,y2) }, { point(0,0), point(offx,0), point(x1,y2-offy), point(x1,y2), point(0,y2) }  },
                    nice_rectangle(x2,y2)
            );
            return object(Rout);
        }
    }
}

pair<poly,poly> triangle_to_nice_triangle(const poly &P) {
    vector<double> sides = side_lengths(P);
    vector<double> tmp = sides;
    int offset = 0;
    rotate( tmp.begin(), tmp.begin()+1, tmp.end() ); if (tmp > sides) sides = tmp, offset = 2;
    rotate( tmp.begin(), tmp.begin()+1, tmp.end() ); if (tmp > sides) sides = tmp, offset = 1;
    rational x = sides[0], y = sides[1], z = sides[2], cx = (x*x + z*z - y*y) / (2*x), cy = sqrt( z*z - cx*cx );
    poly target{ point(0,0), point(x,0), point(cx,cy) };
    poly source{ target[offset], target[(offset+1)%3], target[(offset+2)%3] };
    return {source, target};
}

object triangle_to_nice_triangle(const object &Tin) {
    auto nice = triangle_to_nice_triangle(Tin.P); 
    cout << "tape" << endl;
    cout << "1 " << Tin.ID << endl;
    print_poly(nice.first);
    print_poly(nice.second);
    return object(nice.second);
}

object nice_triangle_to_nice_rectangle(const object &Tin) {
    rational x = real(Tin.P[1]), cx = real(Tin.P[2]), cy = imag(Tin.P[2]);
    cut_and_paste(
            Tin.ID,
            { { point(0,0), point(x,0), point((x+cx)/2,cy/2), point(cx/2,cy/2) }, { point(cx,cy/2), point((x+cx)/2,cy/2), point(cx,cy) }, { point(cx/2,cy/2), point(cx,cy/2), point(cx,cy) } },
            { { point(0,0), point(x,0), point((x+cx)/2,cy/2), point(cx/2,cy/2) }, { point(x,cy/2), point((x+cx)/2,cy/2), point(x,0) },    { point(cx/2,cy/2), point(0,cy/2), point(0,0) }    },
            nice_rectangle(x,cy/2)
    );
    return object(nice_rectangle(x,cy/2));
}

object rectangle_to_nice_triangle(const object &Rin, const poly &tri) {
    poly nice = triangle_to_nice_triangle(tri).second; 
    rational x = real(nice[1]), cx = real(nice[2]), cy = imag(nice[2]);
    
    // normalize the rectangle
    cout << "tape" << endl;
    cout << "1 " << Rin.ID << endl;
    rational width = real(Rin.P[2]) - real(Rin.P[0]), height = imag(Rin.P[2]) - imag(Rin.P[0]);
    print_poly( nice_rectangle(width,height) );
    print_poly( nice_rectangle(width,height) );
    object rect(nice_rectangle(width,height));

    // resize the rectangle
    rect = nice_rectangle_to_nice_rectangle(rect,nice_rectangle(x,width*height/x));

    // cut the rectangle and assemble the triangle
    cut_and_paste(
            rect.ID,
            { { point(0,0), point(x,0), point((x+cx)/2,cy/2), point(cx/2,cy/2) }, { point(x,cy/2), point((x+cx)/2,cy/2), point(x,0) },    { point(cx/2,cy/2), point(0,cy/2), point(0,0) }    },
            { { point(0,0), point(x,0), point((x+cx)/2,cy/2), point(cx/2,cy/2) }, { point(cx,cy/2), point((x+cx)/2,cy/2), point(cx,cy) }, { point(cx/2,cy/2), point(cx,cy/2), point(cx,cy) } },
            nice
    );
    return object(nice);
}

bool is_triangle_ear(const poly &P, point A, point B, point C) {
    if (!counterclockwise(A,B,C)) return false;
    for (point X : P) {
        if (are_equal(A,X) || are_equal(B,X) || are_equal(C,X)) continue;
        if (counterclockwise(A,B,X) && counterclockwise(B,C,X) && counterclockwise(C,A,X)) return false;
    }
    return true;
}

vector<poly> triangulate(poly P) {
    int N = P.size();
    if (N == 3) return {P};
    for (int n=0; n<N; ++n) if (is_triangle_ear(P,P[n],P[(n+1)%N],P[(n+2)%N])) {
        poly Q = P;
        Q.erase( Q.begin()+(n+1)%N );
        vector<poly> answer = triangulate(Q);
        answer.push_back( {P[n],P[(n+1)%N],P[(n+2)%N]} );
        return answer;
    }
    assert(false);
}

vector<object> triangulate_input(const object &Pin) {
    int N = Pin.P.size();
    cout << "scissors" << endl;
    cout << Pin.ID << " " << N-2 << endl;

    vector<object> answer;
    for (poly troj : triangulate(Pin.P)) {
        print_poly(troj);
        answer.push_back(object(troj));
    }
    return answer; 
}

object merge_rectangulation(const vector<object> &RECT) {
    cout << "tape" << endl;
    cout << RECT.size();
    for (auto rect : RECT) cout << " " << rect.ID;
    cout << endl;
    rational dx = 0;
    for (auto rect : RECT) {
        auto P = rect.P;
        rational width = real(P[2]);
        for (auto &pt : P) pt += dx;
        print_poly(P);
        dx += width;
    }
    print_poly(nice_rectangle(dx,dx));
    return object(nice_rectangle(dx,dx));
}

vector<object> split_square(const object &Sin, const vector<poly> &pieces) {
    rational a = real(Sin.P[2]), dx = 0;
    cout << "scissors" << endl;
    cout << Sin.ID << " " << pieces.size() << endl;
    vector<object> answer;
    for (auto tri : pieces) {
        rational width = poly_area(tri) / a;
        auto rect = nice_rectangle(width,a,dx,0);
        print_poly(rect);
        answer.push_back(object(rect));
        dx += width;
    }
    return answer;
}

void merge_triangulation(const vector<object> &have, vector<poly> &want, poly &goal) {
    int N = have.size();
    cout << "tape" << endl;
    cout << N;
    for (auto tri : have) cout << " " << tri.ID;
    cout << endl;
    for (int n=0; n<N; ++n) {
        auto havelen = side_lengths(have[n].P);
        while (true) {
            auto wantlen = side_lengths(want[n]);
            if (are_equal(havelen,wantlen)) break;
            rotate( want[n].begin(), want[n].begin()+1, want[n].end() );
        }
        print_poly(want[n]);
    }
    print_poly(goal);
}

int main() {
    initialize();
    poly start = load_poly();
    poly goal = load_poly();
    object START(start);
    vector<object> TRIANGULATION = triangulate_input(START);
    rational area = poly_area(start);
    rational desired_y = sqrt(area);
    vector<object> RECTANGULATION;
    for (auto tri : TRIANGULATION) {
        object nicetri = triangle_to_nice_triangle(tri);
        object rect = nice_triangle_to_nice_rectangle(nicetri);
        rational rect_area = poly_area(rect.P);
        object rect2 = nice_rectangle_to_nice_rectangle(rect,nice_rectangle(rect_area/desired_y,desired_y));
        RECTANGULATION.push_back(rect2);
    }
    object square = merge_rectangulation(RECTANGULATION);
    vector<poly> output_triangulation = triangulate(goal);
    RECTANGULATION = split_square(square,output_triangulation);
    TRIANGULATION.clear();
    for (unsigned n=0; n<output_triangulation.size(); ++n) TRIANGULATION.push_back(rectangle_to_nice_triangle(RECTANGULATION[n],output_triangulation[n]));
    merge_triangulation(TRIANGULATION,output_triangulation,goal);
}

• 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