/*
	A basic extension of the java.applet.Applet class
 */

import java.awt.*;
import java.applet.*;
import java.util.Vector;
import java.lang.Math;

public class Cut extends Applet
{
    Vector m_pPatterns=new Vector();
    int m_iBottom, m_iRight;
	public void init()
	{
		//{{INIT_CONTROLS
		setLayout(null);
		setSize(700,500);
		textArea1 = new java.awt.TextArea("",0,0,TextArea.SCROLLBARS_VERTICAL_ONLY);
		textArea1.setBounds(600,12,84,480);
		add(textArea1);
		button1 = new java.awt.Button();
		button1.setLabel("Run");
		button1.setBounds(12,456,72,26);
		button1.setBackground(new Color(12632256));
		add(button1);
		button2 = new java.awt.Button();
		button2.setLabel("Clear");
		button2.setBounds(108,456,72,26);
		button2.setBackground(new Color(12632256));
		add(button2);
		//}}
	
		//{{REGISTER_LISTENERS
		SymMouse aSymMouse = new SymMouse();
		button1.addMouseListener(aSymMouse);
		button2.addMouseListener(aSymMouse);
		//}}
		m_iBottom=100;
		m_iRight=100;
	}
	
	//paint function
	public void paint(Graphics g) {
	    Plokste pDummy;
	    Color cColor;

	    cColor=g.getColor();
	    g.setColor(Color.white);
	    for(int i=0; i<10;i++) {
	        g.drawLine(0,i*10,m_iRight,i*10);
	        g.drawLine(i*10,0,i*10,m_iBottom);
	    }
	    g.setColor(cColor);
	    for(int i=0; i<m_pPatterns.size(); i++) {
	        pDummy=(Plokste)m_pPatterns.elementAt(i);
	        if (pDummy.m_bUsed) {
	            if (!pDummy.m_bMeta) {
	                cColor=g.getColor();
	                g.setColor(Color.red);
        	        g.drawRect(pDummy.m_iLeft,pDummy.m_iTop,pDummy.m_iWidth,pDummy.m_iHeight);
        	        g.setColor(cColor);
        	    }
    	    }
	    }
	}
	
	//sort data
	private void Sort() {
	    Plokste p1,p2;
	    for(int i=0; i<m_pPatterns.size(); i++) {
	        for (int j=0; j<m_pPatterns.size(); j++) {
	            p1=(Plokste)m_pPatterns.elementAt(i);
	            p2=(Plokste)m_pPatterns.elementAt(j);
	            if (p1.getLargest()>p2.getLargest()) {
	                m_pPatterns.setElementAt(p1,j);
	                m_pPatterns.setElementAt(p2,i);
	            }
	        }
	    }
	}
	
	//cutting of patterns
	private void CutPatterns() {
	    Plokste p1, p2;
	    int pos;
	    
	    p1=p2=null;
	    for (int i=0; i<m_pPatterns.size(); i++) {
	        if (i==0) {
    	        p1=(Plokste)m_pPatterns.elementAt(i);
    	        if (!p1.m_bUsed) {
    	            p1.setPlokste(0,0,p1.m_iWidth,p1.m_iHeight);
	                p1.m_bUsed=true;
	            }
	        } else {
	            p2=(Plokste)m_pPatterns.elementAt(i);
	            if (!p2.m_bUsed) {
    	            pos=addPatterns(p1, p2);
    	            if (p2.m_bUsed) {
    	                p1=joinPatterns(p1,p2,pos);
    	                //p1=p2;
    	            }
	            }
	        }
	    }
	}
	
	//making from two patterns one meta pattern
	private Plokste joinPatterns(Plokste p1, Plokste p2,int pos) {
	    Plokste p=new Plokste();
	    Plokste pb;
	    
	    switch (pos) {
	        case 1:
	            p.setPlokste(p1.m_iLeft, p1.m_iTop, p1.m_iWidth, p1.m_iHeight+p2.m_iHeight);
	            p.m_bUsed=true;
	            //m_pPatterns.addElement(p);
	        break;
	        case 2:
	            p.setPlokste(p1.m_iLeft, p1.m_iTop, p1.m_iWidth, p1.m_iHeight+p2.m_iHeight);
	            p.m_bUsed=true;
	            //m_pPatterns.addElement(p);
	        break;
	        case 3:
	            p.setPlokste(p1.m_iLeft, p1.m_iTop, p1.m_iWidth, p1.m_iHeight+p2.m_iHeight);
	            p.m_bUsed=true;
	            //m_pPatterns.addElement(p);
	        break;
	        case 4:
	            p.setPlokste(p1.m_iLeft, p1.m_iTop, p1.m_iWidth+p2.m_iWidth, p1.m_iHeight);
	            p.m_bUsed=true;
	            //m_pPatterns.addElement(p);
	        break;
	    }
	    p.m_bMeta=true;
	    for (int i=0; i<m_pPatterns.size(); i++) {
	        pb=(Plokste)m_pPatterns.elementAt(i);
	        if (p.getLargest()>pb.getLargest()) {
        	    m_pPatterns.insertElementAt(p,i);
        	    break;
	        }
	    }
	    return p;
	}
	
	//adding patterns to meta patterns
	private int addPatterns(Plokste p1, Plokste p2) {
	    int commarea, area, dif, pos=0;
	    
	    commarea=p2.m_iWidth*p2.m_iHeight+p1.m_iWidth*p1.m_iHeight;
	    area=getLargest(p1.m_iWidth,p2.m_iWidth)*(p1.m_iHeight+p2.m_iHeight);
	    dif=area;
	    //koordinaciu priskyrimas
	    if (p1.m_iTop+p1.m_iHeight+p2.m_iHeight<=m_iBottom) {
    	    dif=area-commarea;
    	    p2.setPlokste(p1.m_iLeft,p1.m_iTop+p1.m_iHeight,p2.m_iWidth,p2.m_iHeight);
    	    pos=1;
    	    p2.m_bUsed=true;
    	}
	    //pasukam 90 kampu
	    area=getLargest(p1.m_iWidth,p2.m_iHeight)*(p1.m_iHeight+p2.m_iWidth);
	    if (dif>(area-commarea)) {
	        if (p1.m_iTop+p1.m_iHeight+p2.m_iWidth<=m_iBottom) {
    	        dif=area-commarea;
    	        p2.setPlokste(p1.m_iLeft,p1.m_iTop+p1.m_iHeight,p2.m_iHeight,p2.m_iWidth);
    	        pos=2;
    	        p2.m_bUsed=true;
    	    }
	    }
	    //dar syki sukam
	    area=(p1.m_iWidth+p2.m_iWidth)*getLargest(p1.m_iHeight,p2.m_iHeight);
	    if (dif>(area-commarea)) {
	        if (p1.m_iLeft+p1.m_iWidth+p2.m_iWidth<=m_iRight) {
    	        dif=area-commarea;
    	        p2.setPlokste(p1.m_iLeft+p1.m_iWidth,p1.m_iTop,p2.m_iWidth,p2.m_iHeight);
    	        pos=3;
    	        p2.m_bUsed=true;
    	    }
	    }	    
	    //ir dar syki sukam
	    area=(p1.m_iWidth+p2.m_iHeight)*getLargest(p1.m_iHeight,p2.m_iWidth);
	    if (dif>(area-commarea)) {
	        if (p1.m_iLeft+p1.m_iWidth+p2.m_iHeight<=m_iRight) {
    	        dif=area-commarea;
    	        p2.setPlokste(p1.m_iLeft+p1.m_iWidth,p1.m_iTop,p2.m_iHeight,p2.m_iWidth);
    	        pos=4;
    	        p2.m_bUsed=true;
    	    }
	    }
	    return pos;
	}
	
	private int getLargest(int i1, int i2) {
	    if (i1>i2) {
	        return i1;
	    } else {
	        return i2;
	    }
	}
	
	//{{DECLARE_CONTROLS
	java.awt.TextArea textArea1;
	java.awt.Button button1;
	java.awt.Button button2;
	//}}

	class SymMouse extends java.awt.event.MouseAdapter
	{
		public void mouseClicked(java.awt.event.MouseEvent event)
		{
			Object object = event.getSource();
			if (object == button1)
				button1_MouseClicked(event);
			else if (object == button2)
				button2_MouseClicked(event);
		}
	}

	void button1_MouseClicked(java.awt.event.MouseEvent event)
	{
		// to do: code goes here.
	    int iLoc=0;
	    int iRight=0;
	    int iBottom=0;
	    String sDummy=new String();
	    String sValue =new String();
	    Plokste pPlokste;
	    
		sValue=textArea1.getText();
		if (sValue!="") {
		    for (int i=0; i<sValue.length(); i++) {
		        if (sValue.charAt(i)!=10) {
		            if (sValue.charAt(i)!=',') {
    		            sDummy+=sValue.charAt(i);
    		        } else {
    		            iRight=Integer.parseInt(sDummy);
    		            sDummy="";
    		        }
    		    } else {
    		        iBottom=Integer.parseInt(sDummy);
    		        sDummy="";
    		        pPlokste=new Plokste(0,0,iRight,iBottom);
    		        m_pPatterns.addElement(pPlokste);
    		    }
    		}
	        iBottom=Integer.parseInt(sDummy);
	        sDummy="";
	        pPlokste=new Plokste(0,0,iRight,iBottom);
	        m_pPatterns.addElement(pPlokste);
	        //cia gali buti vykdomas cuttingas
	        Sort();
	        CutPatterns();
	        repaint();
	    }
	}

	void button2_MouseClicked(java.awt.event.MouseEvent event)
	{
		// to do: code goes here.
		textArea1.setText("");
		m_pPatterns.removeAllElements();
		repaint();
	}
}

class Plokste {
    int m_iLeft, m_iTop, m_iWidth, m_iHeight;
    boolean m_bUsed;
    boolean m_bMeta;
    public Plokste() {
        m_iLeft=0;
        m_iTop=0;
        m_iWidth=0;
        m_iHeight=0;
        m_bUsed=false;
        m_bMeta=false;
    }
    public Plokste(int left, int top, int width, int height) {
        m_iLeft=left;
        m_iTop=top;
        m_iWidth=width;
        m_iHeight=height;
        m_bUsed=false;
        m_bMeta=false;
    }
    public void setPlokste(int left, int top, int width, int height) {
        m_iLeft=left;
        m_iTop=top;
        m_iWidth=width;
        m_iHeight=height;
    }
    public int getLargest() {
        if (m_iWidth>m_iHeight) {
            return m_iWidth;
        } else {
            return m_iHeight;
        }
    }
}