#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);
}
