import java.io.* ;

class Quad {

    /* Noeud de quad-tree.
     * Pour gérer des images rectangulaires quelconques,
     * on rajoute des noeuds à deux fils pour lesquelles
     * on ne divise le rectangle qu'en deux (soit verticalement,
     * soit horizontalement).
     */

    int nature ;
    final static int LEAF=0, NODE=1, HOR=2, VER=3 ;

    int color ; // Les feuilles
    Quad (int color) {
        this.nature = LEAF ; this.color = color ;
    }

    Quad sw, se, ne, nw ; // Les noeuds internes
    Quad (Quad sw, Quad se, Quad ne, Quad nw) {
        this.nature = NODE ;
        this.sw = sw ; this.nw = nw ;
        this.ne = ne ; this.se = se ;
    }

    static Quad newNod (Quad sw, Quad se, Quad ne, Quad nw, 
                        boolean opt) {
        if (opt && monochrome (sw, se, ne, nw))
            return sw ;
        return new Quad (sw, se, ne, nw) ;
    }

    // Les noeuds horizontaux (nw, ne) :
    static Quad newHor (Quad left, Quad right, boolean opt) {
        if (opt && monochrome (left, right))
            return left ;
        Quad q = new Quad (null, null, right, left) ;
        q.nature = HOR ;
        return q ;
    }
    
    // Les noeuds verticaux (sw, nw) :
    static Quad newVer (Quad bottom, Quad up, boolean opt) {
        if (opt && monochrome (bottom, up))
            return bottom ;
        Quad q = new Quad (bottom, null, null, up) ;
        q.nature = VER ;
        return q ;
    }
    
    static boolean monochrome(Quad q1, Quad q2, Quad q3, Quad q4) {
        return
            (q1.nature == LEAF && q2.nature == LEAF &&
             q3.nature == LEAF && q4.nature == LEAF) &&
            (q1.color == q2.color && q2.color == q3.color &&
             q3.color == q4.color) ;
    }

    static boolean monochrome(Quad q1, Quad q2) {
        return
            (q1.nature == LEAF && q2.nature == LEAF) &&
            (q1.color == q2.color) ;
    }

}

class FenQuad implements Fenetre
{
    int larg, haut ;
    Quad rac ;

    FenQuad (int l, int h) {
        larg = l ;
        haut = l ;
        rac = new Quad (0) ;
    }

    public void rectangle (int xa, int ya, int xb, int yb, int coul) {
        rac = rectangle (rac, 
                         new Point (0, 0), new Point (larg, haut),
                         new Point (xa, ya), new Point (xb, yb), 
                         coul) ;

    }

    static Quad rectangle (Quad q, Point nw, Point se,
                           Point a, Point b, int coul) {
        // Pas d'intersection :
        if (se.x <= a.x || nw.x >= b.x || se.y <= a.y || nw.y >= b.y)
            return q ;
        // q inclus :
        if (nw.x >= a.x && nw.y >= a.y && se.x <= b.x && se.y <= b.y)
            return new Quad (coul) ;
        Point sw = new Point (nw.x, se.y) ;
        Point ne = new Point (se.x, nw.y) ;
        if (q.nature == Quad.NODE) {
            return Quad.newNod (
                rectangle (q.sw, nw.mil (sw), se.mil(sw), a, b, coul),
                rectangle (q.se, nw.mil (se), se, a, b, coul),
                rectangle (q.ne, nw.mil (ne), se.mil(ne), a, b, coul), 
                rectangle (q.nw, nw, se.mil(nw), a, b, coul),
                true) ;
        } else if (q.nature == Quad.HOR) {
            return Quad.newHor (
                rectangle (q.nw, nw, se.mil(sw), a, b, coul),
                rectangle (q.ne, nw.mil (ne), se, a, b, coul),
                true) ;
        } else if (q.nature == Quad.VER) {
            return Quad.newVer (
                rectangle (q.sw, nw.mil (sw), se, a, b, coul),
                rectangle (q.nw, nw, se.mil(ne), a, b, coul),
                true) ;
        } else if (q.nature == Quad.LEAF) {
            if (unPixel (nw, se)) 
                //return new Quad (coul) ;
                throw new Error ("Devrait passer dans inclus.") ;
            q = split (q, nw, se) ;
            return rectangle (q, nw, se, a, b, coul) ;
        } else
            throw new Error ("Nature inconnue " + q.nature) ;
    }

    public void ligne (int xa, int ya, int xb, int yb, int coul) {
        if (Math.abs (yb - ya) <= Math.abs (xb - xa)) {
            ligne (xa, ya, xb, yb, coul, false) ;
        } else {
            ligne (ya, xa, yb, xb, coul, true) ;
        }
    }

    void ligne (int xa, int ya, int xb, int yb, int coul, 
                boolean miroir) {
        if (xa > xb) {
            ligne (xb, yb, xa, ya, coul, miroir) ;
            return ;
        }
        int l = larg ;
        if (miroir)
            l = haut ;
        for (int x = Math.max (0, xa) ; x < Math.min (xb, l) ; x++) {
            float y = ya + ((float)(yb-ya))/(xb-xa)*(x-xa) ;
            if (! miroir) 
                rac = pixel (rac, new Point (0, 0), 
                             new Point (larg, haut),
                             new Point (x, Math.round (y)), coul) ;
            else 
                rac = pixel (rac, new Point (0, 0), 
                             new Point (larg, haut),
                             new Point (Math.round (y), x), coul) ;
        }
    }

    static Quad pixel (Quad q, Point nw, Point se,
                       Point a, int coul) {
        return rectangle (q, nw, se, 
                          a, new Point (a.x+1, a.y+1), coul) ;
    }

    public void triangle (int xa, int ya, int xb, int yb, 
                          int xc, int yc, int coul) {

        rac = triangle (rac, new Point (0, 0), new Point (larg, haut),
                        new Point (xa, ya), 
                        new Point (xb, yb), 
                        new Point (xc, yc), coul) ;

        ligne (xa, ya, xb, yb, coul) ;
        ligne (xb, yb, xc, yc, coul) ;
        ligne (xc, yc, xa, ya, coul) ;
    }

    static Quad triangle (Quad q, Point nw, Point se,
                          Point a, Point b, Point c, int coul) {
        if (Geom.rectInclusTrig (nw, se, a, b, c))
            return new Quad (coul) ; 
        if (! Geom.interTrigRect (a, b, c, nw, se))
            return q ;
        Point sw = new Point (nw.x, se.y) ;
        Point ne = new Point (se.x, nw.y) ;
        if (q.nature == Quad.NODE) {
            return Quad.newNod (
                triangle (q.sw, nw.mil (sw), se.mil(sw), a, b, c, coul),
                triangle (q.se, nw.mil (se), se, a, b, c, coul),
                triangle (q.ne, nw.mil (ne), se.mil(ne), a, b, c, coul), 
                triangle (q.nw, nw, se.mil(nw), a, b, c, coul),
                true) ;
        } else if (q.nature == Quad.HOR) {
            return Quad.newHor (
                triangle (q.nw, nw, se.mil(sw), a, b, c, coul),
                triangle (q.ne, nw.mil (ne), se, a, b, c, coul),
                true) ;
        } else if (q.nature == Quad.VER) {
            return Quad.newVer (
                triangle (q.sw, nw.mil (sw), se, a, b, c, coul),
                triangle (q.nw, nw, se.mil(ne), a, b, c, coul),
                true) ;
        } else if (q.nature == Quad.LEAF) {
            if (unPixel (nw, se))
                return q ; /* Carr'e de bord non inclus dans le 
                            * triangle, 'eventuellement color'e par 
                            * les appels `a ligne() sur les bords. */
            q = split (q, nw, se) ;
            return triangle (q, nw, se, a, b, c, coul) ;
        } else
            throw new Error ("Nature inconnue " + q.nature) ;
    }

    static boolean unPixel (Point nw, Point se) {
        return (se.x == nw.x + 1) && (se.y == nw.y + 1) ;  
    }

    static Quad split (Quad q, Point nw, Point se) {
        int dx = se.x - nw.x, dy = se.y - nw.y ;
        if (dx >= 2*dy) { // horizontal
            return Quad.newHor (q, q, false) ;
        } else if (dy >= 2*dx) { // vertical
            return Quad.newVer (q, q, false) ;
        } else { // quad
            return Quad.newNod (q, q, q, q, false) ;
        }
    }

    void copieVers (Fenetre f) {
        copieVers (rac, new Point (0, 0), new Point (larg, haut), f) ;
    }

    static void copieVers (Quad q, Point nw, Point se, Fenetre f) {
        Point sw = new Point (nw.x, se.y) ;
        Point ne = new Point (se.x, nw.y) ;
        if (q.nature == Quad.NODE) {
            copieVers (q.sw, nw.mil (sw), se.mil(sw), f) ;
            copieVers (q.se, nw.mil (se), se, f) ;
            copieVers (q.ne, nw.mil (ne), se.mil(ne), f) ; 
            copieVers (q.nw, nw, se.mil(nw), f) ;
        } else if (q.nature == Quad.HOR) {
            copieVers (q.nw, nw, se.mil(sw), f) ;
            copieVers (q.ne, nw.mil (ne), se, f) ;
        } else if (q.nature == Quad.VER) {
            copieVers (q.sw, nw.mil (sw), se, f) ;
            copieVers (q.nw, nw, se.mil(ne), f) ;
        } else if (q.nature == Quad.LEAF) {
            f.rectangle (nw.x, nw.y, se.x, se.y, q.color) ;
        } else
            throw new Error ("Nature inconnue " + q.nature) ;
    }

    void write (OutputBits out) throws IOException {
        out.write16 (larg) ;
        out.write16 (haut) ;
        write (rac, out) ;
    }

    /* Ecriture pr'efixe sw se ne nw :
     */
    static void write (Quad q, OutputBits out) throws IOException {
        // out.write2 (q.nature) ;
        /* Optimisation Huffmanienne (il y a beaucoup plus
         * de noeuds de nature NODE que des autres) :  */
        if (q.nature == Quad.NODE) {
            out.write1 (1) ; // 10
            out.write1 (0) ;
            write (q.sw, out) ;
            write (q.se, out) ;
            write (q.ne, out) ; 
            write (q.nw, out) ;
        } else if (q.nature == Quad.HOR) {
            out.write1 (1) ; // 110
            out.write1 (1) ;
            out.write1 (0) ;
            write (q.nw, out) ;
            write (q.ne, out) ;
        } else if (q.nature == Quad.VER) {
            out.write1 (1) ; // 111
            out.write1 (1) ;
            out.write1 (1) ;
            write (q.sw, out) ;
            write (q.nw, out) ;
        } else if (q.nature == Quad.LEAF) {
            out.write1 (0) ; // 0
            out.write8 (q.color) ;
        } else
            throw new Error ("Nature inconnue " + q.nature) ;
    }

    void save (String file) {
        try {
            OutputBits out = 
                new OutputBits (new FileOutputStream (file)) ;
            write (out) ;
            out.close () ;
        } catch (IOException e) {
            throw new Error (e) ;
        }
    }

    static FenQuad load (String file) {
        try {
            return read (new InputBits (new FileInputStream (file))) ;
        } catch (IOException e) {
            throw new Error (e) ;
        }
    }

    static FenQuad read (InputBits inp) throws IOException {
        FenQuad f = new FenQuad (inp.read16(), inp.read16()) ;
        f.rac = readQuad (inp) ;
        return f ;
    }

    /* Lecture pr'efixe sw se ne nw :
     */
    static Quad readQuad (InputBits inp) throws IOException {
        // int nature = inp.read2 () ;
        // Optimisation Huffmanienne (voir writeQuad) :
        int nature ;
        if (inp.read1() == 0) { // 0
            nature = Quad.LEAF ;
        } else if (inp.read1() == 0) { // 10
            nature = Quad.NODE ;
        } else if (inp.read1() == 0) { // 110
            nature = Quad.HOR ;
        } else { // 111
            nature = Quad.VER ;
        }
        //System.out.println ("r " + nature) ;
        if (nature == Quad.NODE) {
            return Quad.newNod (readQuad (inp), readQuad (inp), 
                           readQuad (inp), readQuad (inp),
                           false) ;
        } else if (nature == Quad.HOR) {
            return Quad.newHor (readQuad (inp), readQuad (inp), false) ;
        } else if (nature == Quad.VER) {
            return Quad.newVer (readQuad (inp), readQuad (inp), false) ;
        } else if (nature == Quad.LEAF) {
            return new Quad (inp.read8 ()) ;
        } else
            throw new Error ("Nature inconnue " + nature) ;
    }


    public static void main (String[] args) {
        FenQuad f ;
        if (args.length == 1) {
            f = load (args[0]) ;
        } else {
            f = new FenQuad (420, 400) ;
/*
            f.ligne (3,10, 30,300, 1) ;
            f.ligne (3,20, 50,21, 1) ;
            f.triangle (3,50, 50,51, 10,100, 2) ;
            f.triangle (100,10, 130,10, 130,40, 2) ;
            f.triangle (100,10, 100,40, 130,40, 2) ;
            f.rectangle (100,100, 130,140, 30) ;
            f.ligne (50,51, 10,100, 1) ;
            f.save ("fen.quad") ;
*/
            FilePrio fp = new FilePrio (10000) ;
/*
            fp.ajouter (new Pyramide (1, 100, 10, 
                                      new Point (160, 160), new Point (40, 40),
                                      2., .8, 2, 6)) ;

            fp.ajouter (new Pyramide (2, 100, 10, 
                                      new Point (200, 180), new Point (120, 40),
                                      2., .8, 85, 6)) ;

            fp.ajouter (new Sierpinski (0, 70, 10,
                                        new Point(40,0),  
                                        new Point (120,400), 
                                        new Point (400,80),  
                                        2, 255)) ;
*/
        fp.ajouter (new Entrelas (1, 11, 10, 
                                  new Point (88, 100), new Point (8, 40),
                                  2., .8, 2, 6)) ;

            while (fp.nonVide ()) {
                Evenement e = fp.retirerMin () ;
                e.effectuer (f, fp) ;
            }

        }
        System.out.println ("Affichage.") ;
        FenEcran ecr = new FenEcran (Math.max (f.larg, f.haut)) ;
        f.copieVers (ecr) ;

        // Pour comparer la taille avec une compression classique :
        f.save ("fen.quad") ;
        ecr.save ("fen.png") ;
    }

}

class OutputBits 
{
    OutputStream out ; // ou 'ecrire
    int curByte ; // byte en cours
    int n ;  // nb bits `a 'ecrire dans curByte

    OutputBits (OutputStream o) {
        out = o ;
        curByte = 0 ;
        n = 0 ;
    }

    // 'Ecrire un bit (i = 0 ou 1).
    void write1 (int i) throws IOException { 
        curByte = (curByte << 1) + i ; // bits de poids fort en premier
        n++ ;
        if (n == 8) {
            out.write (curByte) ;
            curByte = 0 ;
            n = 0 ;
        }
    }

    void write2 (int i) throws IOException {
        write1 (i >> 1) ;
        write1 (i & 1) ;
    }

    void write4 (int i) throws IOException {
        write2 (i >> 2) ;
        write2 (i & 3) ;
    }

    void write8 (int i) throws IOException {
        write4 (i >> 4) ;
        write4 (i & 0xf) ;
    }

    void write16 (int i) throws IOException {
        write8 (i >> 8) ;
        write8 (i & 0xff) ;
    }

    public void finalize () throws IOException {
        close () ;
    }

    // On rajoute des z'eros pour finir le byte.
    void close () throws IOException {
        if (n > 0) {
            while (n < 7)
                write1 (0) ;
            write1 (0) ;
        }
        out.close () ;
    }
}

class InputBits 
{
    InputStream inp ; // ou lire
    int curByte ; // byte en cours
    int n ;  // nb bits restant `a lire dans curByte

    InputBits (InputStream o) {
        inp = o ;
        curByte = 0 ;
        n = 0 ;
    }

    // 'Ecrire un bit (i = 0 ou 1).
    int read1 () throws IOException { 
        if (n == 0) {
            curByte = inp.read () ;
            if (curByte == -1)
                throw new Error ("Fin pr'ematur'ee de fichier.") ;
            n = 8 ;
        }
        n-- ;
        return (curByte >> n) & 1 ;
    }

    int read2 () throws IOException {
        return (read1() << 1) + read1() ; 
    }

    int read4 () throws IOException {
        return (read2() << 2) + read2() ; 
    }

    int read8 () throws IOException {
        return (read4() << 4) + read4() ; 
    }

    int read16 () throws IOException {
        return (read8() << 8) + read8() ; 
    }

}

class Geom
{
    // ----------------- G'eometrie ----------------------------

    /* Teste si l'angle b a c (entre les vecteurs ab et ac) 
     * est positif. Il suffit de calculer le produit vectoriel.
     * Si l'angle est nul, on compare les normes.
     */
    static int anglePos (Point a, Point b, Point c) {
        int dx1 = b.x - a.x; int dy1 = b.y - a.y;
        int dx2 = c.x - a.x; int dy2 = c.y - a.y;
        if (dx1 * dy2 > dy1 * dx2) return 1;
        else if (dx1 * dy2 < dy1 * dx2) return -1;
        else { 
            if (dx1 * dx2 < 0 || dy1 * dy2 < 0) return -1;
            else if (dx1*dx1 + dy1*dy1 >= dx2*dx2 + dy2*dy2) return 0;
            else return 1;
        }
    }

    /* Test d'intersection de deux segments ab et cd :
     * on teste si les extr'emit'es de l'un sont de part et d'autre
     * de l'autre.
     */
    static boolean interSegSeg (Point a, Point b, Point c, Point d) {
        return  anglePos (a, b, c) * anglePos (a, b, d) <= 0
            && anglePos (c, d, a) * anglePos (c, d, b) <= 0 ;
    }

    /* Teste si le point p est dans l'int'erieur du triangle abc.
     */
    static boolean dansTriangle (Point p, Point a, Point b, Point c) {
        return  anglePos (a, p, b) * anglePos (a, p, c) <= 0
            && anglePos (b, p, c) * anglePos (b, p, a) <= 0
            && anglePos (c, p, a) * anglePos (c, p, b) <= 0 ;
    }

    /* Teste si le rectangle horizontal 
     * de coins nw inclus et se exclus
     * est inclus dans le triangle abc.
     */
    static boolean rectInclusTrig (Point nw, Point se, 
                                   Point a, Point b, Point c) {
        Point sem1 = new Point (se.x-1, se.y-1) ;
        Point swm1 = new Point (nw.x, sem1.y) ;
        Point nem1 = new Point (sem1.x, nw.y) ;
        return dansTriangle (swm1, a, b, c) 
            && dansTriangle (sem1, a, b, c) 
            && dansTriangle (nem1, a, b, c) 
            && dansTriangle (nw, a, b, c) ;
    }


    /* Teste si le triangle abc recouvre m^eme partiellement
     * le rectangle horizontal de coins nw et se.
     */
    static boolean interTrigRect (Point a, Point b, Point c,
                                   Point nw, Point se) {
        return dansTriangle (nw, a, b, c) 
            || dansTriangle (se, a, b, c)
            || interSegRect (a, b, nw, se)
            || interSegRect (b, c, nw, se)
            || interSegRect (c, a, nw, se) ;
    }

    /* Teste si le segment ab intersecte le rectangle
     * horizontal de coins nw et se.
     */
    static boolean interSegRect (Point a, Point b, 
                                  Point nw, Point se) {
        if (dansRect (a, nw, se) || dansRect (b, nw, se))
            return true ;
        Point ne = new Point (se.x, nw.y) ;
        Point so = new Point (nw.x, se.y) ;
        return interSegSeg (a, b, nw, ne)
            || interSegSeg (a, b, ne, se)
            || interSegSeg (a, b, se, so)
            || interSegSeg (a, b, so, nw) ;
    }

    /* Teste si le point a est dans l'int'erieur du rectangle
     * horizontal de coins nw et se.
     * ((0,0) est au nw et (infini,infini) au se.)
     */
    static boolean dansRect (Point a, Point nw, Point se) {
        return a.x > nw.x && a.x < se.x
            && a.y > nw.y && a.y < se.y ;
    }

    public static void main (String[] args) {
        Point o = new Point (0, 0) ;
        Point i = new Point (10, 0) ;
        Point k = new Point (10, 10) ;
        Point j = new Point (0, 10) ;
        System.out.println (dansTriangle (new Point (5,0),
                                          o,i,k)) ;
        System.out.println (interSegSeg (new Point (-10,10),
                                         new Point (20, 10),j,k)) ;
        System.out.println (interTrigRect (new Point (-100,-100),
                                           new Point (-100, 100),
                                           new Point (100, 0),
                                          j, i)) ;
        for (int y=-1; y<=1 ; y++)
            for (int x=-1 ; x<=1 ; x++)
                if (dansTriangle (new Point (x, y), o, i, k))
                    System.out.println (x + " " + y) ;
    }

}