#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
struct Shape{
int ID;
vector<pii> pt;
Shape(int _ID, vector<pii> _pt) : ID(_ID), pt(_pt) {}
};
int IDs;
vector<Shape> qu;
inline int dx(Shape SS){
return (SS.pt[1].F - SS.pt[0].F);
}
inline int dy(Shape SS){
return (SS.pt[2].S - SS.pt[1].S);
}
void scissors(Shape from, vector<Shape> to){
cout<<"scissors"<<'\n';
cout<<from.ID<<" "<<szof(to)<<'\n';
for(Shape SS : to){
cout<<szof(SS.pt)<<" ";
for(pii p : SS.pt){
cout<<p.F<<" "<<p.S<<" ";
}
cout<<'\n';
}
}
void tape(vector<Shape> from, Shape to){
cout<<"tape"<<'\n';
cout<<szof(from)<<" ";
for(Shape SS : from){
cout<<SS.ID<<" ";
}
cout<<'\n';
for(Shape SS : from){
cout<<szof(SS.pt)<<" ";
for(pii p : SS.pt){
cout<<p.F<<" "<<p.S<<" ";
}
cout<<'\n';
}
cout<<szof(to.pt)<<" ";
for(pii p : to.pt){
cout<<p.F<<" "<<p.S<<" ";
}
cout<<'\n';
}
Shape Flip(Shape SS){
Shape ret = SS;
ret.ID = IDs;
IDs++;
int _x = SS.pt[0].F;
int _y = SS.pt[0].S;
int _dx = dx(SS);
int _dy = dy(SS);
SS.pt[1] = mkp(_x + _dy, _y);
SS.pt[2] = mkp(_x + _dy, _y + _dx);
SS.pt[3] = mkp(_x, _y + _dx);
ret.pt[1] = mkp(_x + _dy, _y);
ret.pt[2] = mkp(_x + _dy, _y + _dx);
ret.pt[3] = mkp(_x, _y + _dx);
tape({SS}, ret);
return ret;
}
Shape Move(Shape SS, int move_x, int move_y){
Shape ret = SS;
ret.ID = IDs;
IDs++;
for(pii& p : SS.pt){
p.F += move_x;
p.S += move_y;
}
for(pii& p : ret.pt){
p.F += move_x;
p.S += move_y;
}
tape({SS}, ret);
return ret;
}
vector<Shape> Cut_x(Shape from, int cut_sz){
Shape S0 = from;
Shape S1 = from;
int _x = from.pt[0].F;
S0.ID = IDs;
IDs++;
S0.pt[1].F = _x + cut_sz;
S0.pt[2].F = _x + cut_sz;
S1.ID = IDs;
IDs++;
S1.pt[0].F = _x + cut_sz;
S1.pt[3].F = _x + cut_sz;
scissors(from, {S0, S1});
return {S0, S1};
}
vector<Shape> Cut_y(Shape from, int cut_sz){
Shape S0 = from;
Shape S1 = from;
int _y = from.pt[0].S;
S0.ID = IDs;
IDs++;
S0.pt[2].S = _y + cut_sz;
S0.pt[3].S = _y + cut_sz;
S1.ID = IDs;
IDs++;
S1.pt[0].S = _y + cut_sz;
S1.pt[1].S = _y + cut_sz;
scissors(from, {S0, S1});
return {S0, S1};
}
void solve(Shape SS, Shape TT){
/*
cerr<<endl;
cerr<<"solve "<<endl;
for(pii p : SS.pt){
cerr<<p.F<<" "<<p.S<<" ";
}
cerr<<endl;
for(pii p : TT.pt){
cerr<<p.F<<" "<<p.S<<" ";
}
cerr<<endl;
cerr<<endl;
*/
/// end of recursion
if(dx(SS) == dx(TT) and dy(SS) == dy(TT)){
qu.pb(SS);
return;
}
/// flip SS if necessary
int area0 = min(dx(SS), dx(TT)) * min(dy(SS), dy(TT));
int area1 = min(dy(SS), dx(TT)) * min(dx(SS), dy(TT));
if(area0 < area1){
SS = Flip(SS);
}
/// cut SS and update TT
vector<Shape> Cut;
if(dx(SS) > dx(TT)){
Cut = Cut_x(SS, dx(TT));
qu.pb(Cut[0]);
TT.pt[0].S += dy(SS);
TT.pt[1].S += dy(SS);
}
else if(dx){
Cut = Cut_y(SS, dy(TT));
qu.pb(Cut[0]);
TT.pt[0].F += dx(SS);
TT.pt[3].F += dx(SS);
}
/// move Cut[1] to TT
int move_x = TT.pt[0].F - Cut[1].pt[0].F;
int move_y = TT.pt[0].S - Cut[1].pt[0].S;
Cut[1] = Move(Cut[1], move_x, move_y);
/// recurse
solve(Cut[1], TT);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int sz;
vector<pii> _pt;
/// input SS
cin>>sz;
_pt.resize(sz);
FOR(i, 0, sz-1, 1){
cin>>_pt[i].F>>_pt[i].S;
}
//
assert(_pt[2].F == 3);
assert(_pt[2].S == 8);
//
Shape SS(0, _pt);
IDs = 1;
/// input TT
cin>>sz;
_pt.resize(sz);
FOR(i, 0, sz-1, 1){
cin>>_pt[i].F>>_pt[i].S;
}
Shape TT(-1, _pt);
/// solve
solve(SS, TT);
/// tape
tape(qu, TT);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Operation 3 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '3.000000' vs '2.000000', error '0.333333' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Operation 3 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '3.000000' vs '2.000000', error '0.333333' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Operation 3 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '3.000000' vs '2.000000', error '0.333333' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Operation 3 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '3.000000' vs '2.000000', error '0.333333' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Operation 3 (tape), polygon 0, vertex 0: Equivalent polygons must not change distance of any side by more than 0.001000, got '3.000000' vs '2.000000', error '0.333333' |
| 2 |
Halted |
0 ms |
0 KB |
- |
