import javax.swing.JFrame;
import javax.swing.JComponent;
import java.awt.Graphics;

public class Assignment5 {
    private class Square {
        public int x;
        public int y;
        public int length;
    }

    private static class MyCanvas extends JComponent {
        public Square[] array;
        public void paintComponent(Graphics g) {
            for (int i = 0; i < array.length; i++) {
                g.drawRect(array[i].x*10, array[i].y*10, array[i].length * 10, array[i].length*10);
            }
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        Assignment5 ass5 = new Assignment5();
        Square[] squares = ass5.solveSquare(0, 0, 4, 4, true);

        JFrame window = new JFrame();
        window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        window.setBounds(30, 30, 300, 300);
        MyCanvas canvas = new MyCanvas();
        canvas.array = squares;
        window.getContentPane().add(canvas);
        window.setVisible(true);
        for (int i = 0; i < squares.length; i++) {
            System.out.println(squares[i].x + ", " + squares[i].y + ", " + squares[i].length);
        }
    }

    public Square[] solveSquare(int x, int y, int len, int wid, boolean first) {
        int least = len*wid;
        Square[] rect1, rect2;
        Square[] returnArray = new Square[len*wid];
        int num;
        int min;

        if (!first) {
            if (len == wid) {
                Square square = new Square();
                square.x = x;
                square.y = y;
                square.length = len;
                returnArray = new Square[1];
                returnArray[0] = square;
                return returnArray;
            }

            if(len == 1) {
                returnArray = new Square[wid];
                for (int i = 0; i < wid; i++) {
                    Square square = this.new Square();
                    square.x = x;
                    square.y = y+i;
                    square.length = 1;
                    returnArray[i] = square;
                }
                return returnArray;
            } else if (wid == 1) {
                returnArray = new Square[len];
                for (int i = 0; i < len; i++) {
                    Square square = new Square();
                    square.x = x+i;
                    square.y = y;
                    square.length = 1;
                    returnArray[i] = square;
                }
                return returnArray;
            }
        }

        if (len <= wid) {
            min = len;
        } else {
            min = wid;
        }

        for (int i = min; i >= 1; i--) {
            if (i == min && first) {
                continue;
            }

            rect1 = solveSquare(i+x, y, len-i, wid, false);
            rect2 = solveSquare(x, i+y, i, wid-i, false);
            num = rect1.length + rect2.length;
            if (num <= least) {
                least = num;
                Square square = new Square();
                square.x = 0;
                square.y = 0;
                square.length = i;
                Square[] tempArray = new Square[1];
                tempArray[0] = square;
                returnArray = mergeArrays(rect1, rect2);
                returnArray = mergeArrays(returnArray, tempArray);
            }
        }

        return returnArray;
    }

    private Square[] mergeArrays(Square[] arg1, Square[] arg2)
    {
        Square[] merged = new Square[arg1.length + arg2.length];
        for(int i = 0; i < arg1.length; i++) {
            merged[i] = arg1[i];
        }

        for(int i = 0; i < arg2.length; i++) {
            merged[arg1.length + i] = arg2[i];
        }

        return merged;
    }
}