시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 53 | 10 | 9 | 23.684% |
Given a rectangle with integer side lengths, your task is to cut it into the smallest possible number of squares with integer side lengths.
The first line contains a single integer T — the number of test cases (1 ≤ T ≤ 3600). Each of the next T lines contains two integers wi, hi — the dimensions of the rectangle (1 ≤ wi, hi ≤ 60; for any i ≠ j, either wi ≠ wj or hi ≠ hj ).
For the i-th test case, output ki — the minimal number of squares, such that it is possible to cut the wi by hi rectangle into ki squares. The following ki lines should contain three integers each: xij , yij — the coordinates of the bottom-left corner of the j-th square and lij — its side length (0 ≤ xij ≤ wi − lij ; 0 ≤ yij ≤ hi −lij ). The bottom-left corner of the rectangle has coordinates (0, 0) and the top-right corner has coordinates (wi, hi).
3 5 3 5 6 4 4
4 0 0 3 3 0 2 3 2 1 4 2 1 5 0 0 2 0 2 2 0 4 2 2 0 3 2 3 3 1 0 0 4
Example case 1
Example case 2
Example case 3