/*
Rods (IOI 2002)
Copyright (C) 2003 Stefano Maggiolo

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA


Il problema si risolve in 3 diverse fasi: nella prima vengono
ricercate le coordinate dei vertici del più piccolo rettangolo contenente le
barre; nella seconda viene definita la posizione reciproca delle barre
all'interno del rettangolo; nella terza si individuano le coordinate degli 
estremi delle barre ancora mancanti dal secondo punto.

Nella prima fase vengono ricercate le coordinate dei vertici del rettangolo
contenitore attraverso 4 ricerche dicotomiche, con l'accortezza di
limitare il campo del margine inferiore, che ovviamente non può
essere sopra del margine superiore ed analogalmente per i margini sull'asse orizzontale.

Nella seconda fase si ottengono i valori dei 4 angoli del rettangolo
appena trovato, da cui (tranne in qualche caso in cui è necessaria
un'altra chiamata) si trova la forma, cioè la posizione reciproca
delle due barre, che verrà memorizzata nella variabile f e codificata
(a meno di rotazioni e flip) in questo modo:
f = 0:
          +---+
          | * |
          |***|
          | * |
          +---+

f = 1:
          +---+
          |***|
          |   |
          |*  |
          |*  |
          +---+

f = 2:
          +---+
          | **|
          |*  |
          |*  |
          +---+

f = 3:
          +---+
          |***|
          |   |
          | * |
          | * |
          +---+

La terza fase, basandosi sulla disposizione delle barre, cercherà,
sfruttando la ricerca dicotomica già utilizzata precedentemente ed
altre due funzioni, le coordinate ancora non note delle barre, usando
mediamente due ricerche.

Il numero di richieste totali sarà minore di circa 6 * log N,
che per N pari a 10000 vale circa 80, consentendoci quindi il
punteggio pieno anche nei casi pessimi (il massimo numero di chiamate
negli input reali è 93).

*/

#include <stdio.h>
#include "crectlib.h"

/* macro per non passare sempre ogni parametro +1 */
#define mrect(a, b, c, d) rect((a) + 1, (b) + 1, (c) + 1, (d) + 1)
#define mreport(a, b, c, d, e, f, g, h) \
          report((a) + 1, (b) + 1, (c) + 1, (d) + 1, \
                 (e) + 1, (f) + 1, (g) + 1, (h) + 1)

int N; /* dimensioni della griglia */
int f; /* forma delle barre */
int cr1, cr2, cc1, cc2; /* coordinate del rettangolo contenitore */
int aNO, aSO, aSE, aNE; /* presenza o meno di una barra negli angoli */
int r1c1, r1c2, r1r; /* coordinate della prima barra */
int r2r1, r2r2, r2c; /* coordinate della seconda barra */

/*****************************************************************************/

/*
  cerca una riga r (compresa tra r1 e r2) contenente una barra e tale
  che r - 1 non contiene barre
*/
int
confine_sup(int r1, int r2)
{   int c;
    if (r1 > r2) return r1;
    while (r1 != r2)
    {   c = (r1 + r2) / 2;
        if (mrect(r1, c, 0, N - 1))
            r2 = c;
        else
            r1 = c + 1;
    }
    if (mrect(r1, r1, 0, N - 1))
        return r1;
    else
        return r1 + 1;
}       

/*
  cerca una riga r (compresa tra r1 e r2) contenente una barra e tale
  che r + 1 non contiene barre
*/
int
confine_inf(int r1, int r2)
{   int c;
    if (r1 > r2) return r1;
    while (r1 != r2)
    {   c = (r1 + r2 + 1) / 2;
        if (mrect(c, r2, 0, N - 1))
            r1 = c;
        else
            r2 = c - 1;
    }
    if (mrect(r1, r1, 0, N - 1))
        return r1;
    else
        return r1 + 1;
}       

/*
  cerca una colonna c (compresa tra c1 e c2) contenente una barra e
  tale che c - 1 non contiene barre
*/
int
confine_sx(int c1, int c2)
{   int c;
    if (c1 > c2) return c1;
    while (c1 != c2)
    {   c = (c1 + c2) / 2;
        if (mrect(0, N - 1, c1, c))
            c2 = c;
        else
            c1 = c + 1;
    }
    if (mrect(0, N - 1, c1, c1))
        return c1;
    else
        return c1 + 1;
}

/*
  cerca una colonna c (compresa tra c1 e c2) contenente una barra e
  tale che c + 1 non contiene barre
*/
int
confine_dx(int c1, int c2)
{   int c;
    if (c1 > c2) return c1;
    while (c1 != c2)
    {   c = (c1 + c2 + 1) / 2;
        if (mrect(0, N - 1, c, c2))
            c1 = c;
        else
            c2 = c - 1;
    }
    if (mrect(0, N - 1, c1, c1))
        return c1;
    else
        return c1 + 1;
}       

/* ricerca il rettangolo contenitore */
void
confini(void)
{   cr1 = confine_sup(0, N - 1);
    cr2 = confine_inf(cr1 + 1, N - 1);
    cc1 = confine_sx(0, N - 1);
    cc2 = confine_dx(cc1 + 1, N - 1);
}

/*****************************************************************************/

/*
  cerca nella riga r, tra le colonne c1 e c2, l'unica colonna che
  contiene una barra
*/
int
trova_singolo_in_riga(int c1, int c2, int r)
{   int m = (c1 + c2) / 2;
    if (c1 == c2)
        return c1;
    else if (mrect(r, r, c1, m))
        return trova_singolo_in_riga(c1, m, r);
    else
        return trova_singolo_in_riga(m + 1, c2, r);
}

/*
  cerca nella colonna c, tra le righe r1 e r2, l'unica riga che
  contiene una barra
*/
int
trova_singolo_in_colonna(int r1, int r2, int c)
{   int m = (r1 + r2) / 2;
    if (r1 == r2)
        return r1;
    else if (mrect(r1, m, c, c))
        return trova_singolo_in_colonna(r1, m, c);
    else
        return trova_singolo_in_colonna(m + 1, r2, c);
}

/* determina la posizione reciproca delle barre, esaminando gli angoli */
void
forma(void)
{   aNO = mrect(cr1, cr1, cc1, cc1);
    aSO = mrect(cr2, cr2, cc1, cc1);
    aSE = mrect(cr2, cr2, cc2, cc2);
    if (aNO + aSO + aSE == 0)
        aNE = 0;
    else if (aNO + aSO + aSE == 1)
        aNE = 1;
    else
        aNE = mrect(cr1, cr1, cc2, cc2);
    if (aNO + aSO + aSE + aNE == 0)
        f = 0;
    else if (aNO + aSO + aSE + aNE == 3)
        f = 1;
    else
        if (aNO == aSE)
            f = 2;
        else
            f = 3;
}

/*
  partendo dalla forma, con centinaia di divertenti if, ottiene le
  coordinate mancanti, e chiama report
*/
void
risolvi(void)
{   
    if (f == 0)
    {   /*
          +---+
          | * |
          |***|
          | * |
          +---+
        */
        r2c = trova_singolo_in_riga(cc1 + 1, cc2 - 1, cr1);
        r1r = trova_singolo_in_colonna(cr1 + 1, cr2 - 1, cc1);
        mreport(r1r, cc1, r1r, cc2, cr1, r2c, cr2, r2c);
    }
    else if (f == 1)
        if (aNO == 0)
        {   /*
              +---+
              |  *|
              |  *|
              |***|
              +---+
            */
            r1c2 = confine_dx(cc1 + 1, cc2 - 1);
            if (r1c2 == cc2 - 1)
            {   r1c2++;
                r2r2 = confine_inf(cr1 + 1, cr2 - 1);
                if (r2r2 == cr2 - 1)
                    r2r2++;
                mreport(cr2, cc1, cr2, r1c2, cr1, cc2, r2r2, cc2);
            }
            else
                mreport(cr2, cc1, cr2, r1c2, cr1, cc2, cr2, cc2);
        }
        else if (aSO == 0)
        {   /*
              +---+
              |***|
              |  *|
              |  *|
              +---+
            */
            r1c2 = confine_dx(cc1 + 1, cc2 - 1);
            if (r1c2 == cc2 - 1)
            {   r1c2++;
                r2r1 = confine_sup(cr1 + 1, cr2 - 1);
                if (r2r1 == cr1 + 1)
                    r2r1--;
                mreport(cr1, cc1, cr1, r1c2, r2r1, cc2, cr2, cc2);
            }
            else
                mreport(cr1, cc1, cr1, r1c2, cr1, cc2, cr2, cc2);
        }
        else if (aNE == 0)
        {   /*
              +---+
              |*  |
              |*  |
              |***|
              +---+
            */
            r1c1 = confine_sx(cc1 + 1, cc2 - 1);
            if (r1c1 == cc1 + 1)
            {   r1c1--;
                r2r2 = confine_inf(cr1 + 1, cr2 - 1);
                if (r2r2 == cr2 - 1)
                    r2r2++;
                mreport(cr2, r1c1, cr2, cc2, cr1, cc1, r2r2, cc1);
            }
            else
                mreport(cr2, r1c1, cr2, cc2, cr1, cc1, cr2, cc1);
        }
        else
        {   /*
              +---+
              |***|
              |*  |
              |*  |
              +---+
            */
            r1c1 = confine_sx(cc1 + 1, cc2 - 1);
            if (r1c1 == cc1 + 1)
            {   r1c1--;
                r2r1 = confine_sup(cr1 + 1, cr2 - 1);
                if (r2r1 == cr1 + 1)
                    r2r1--;
                mreport(cr1, r1c1, cr1, cc2, r2r1, cc1, cr2, cc1);
            }
            else
                mreport(cr1, r1c1, cr1, cc2, cr1, cc1, cr2, cc1);
        }
    else if (f == 2)
        if (aNO == 1)
            if (mrect(cr1 + 1, cr1 + 1, cc1, cc1))
            {   /*
                  +---+
                  |*  |
                  |*  |
                  | **|
                  +---+
                */
                r2r2 = confine_inf(cr1 + 1, cr2 - 1);
                r1c1 = confine_sx(cc1 + 1, cc2 - 1);
                mreport(cr2, r1c1, cr2, cc2, cr1, cc1, r2r2, cc1);
            }
            else
            {   /*
                  +---+
                  |** |
                  |  *|
                  |  *|
                  +---+
                */
                r2r1 = confine_sup(cr1 + 1, cr2 - 1);
                r1c2 = confine_dx(cc1 + 1, cc2 - 1);
                mreport(cr1, cc1, cr1, r1c2, r2r1, cc2, cr2, cc2);
            }
        else
            if (mrect(cr1 + 1, cr1 + 1, cc2, cc2))
            {   /*
                  +---+
                  |  *|
                  |  *|
                  |** |
                  +---+
                */
                r2r2 = confine_inf(cr1 + 1, cr2 - 1);
                r1c2 = confine_dx(cc1 + 1, cc2 - 1);
                mreport(cr2, cc1, cr2, r1c2, cr1, cc2, r2r2, cc2);
            }
            else
            {   /*
                  +---+
                  | **|
                  |*  |
                  |*  |
                  +---+
                */
                r2r1 = confine_sup(cr1 + 1, cr2 - 1);
                r1c1 = confine_sx(cc1 + 1, cc2 - 1);
                mreport(cr1, r1c1, cr1, cc2, r2r1, cc1, cr2, cc1);
            }
                
    else if (f == 3)
    {
        if (aNO == 1)
            if (aSO == 1)
            {   /*
                  +----+
                  |*   |
                  |* **|
                  |*   |
                  +----+
                */
                r1r = trova_singolo_in_colonna(cr1 + 1, cr2 - 1, cc2);
                r1c1 = confine_sx(cc1 + 1, cc2 - 1);
                if (r1c1 == cc1 + 1)
                    r1c1--;
                mreport(r1r, r1c1, r1r, cc2, cr1, cc1, cr2, cc1);
            }
            else
            {   /*
                  +---+
                  |***|
                  |   |
                  | * |
                  | * |
                  +---+
                */
                r2c = trova_singolo_in_riga(cc1 + 1, cc2 - 1, cr2);
                r2r1 = confine_sup(cr1 + 1, cr2 - 1);
                if (r2r1 == cr1 + 1)
                    r2r1--;
                mreport(cr1, cc1, cr1, cc2, r2r1, r2c, cr2, r2c);
            }
        else
            if (aSO == 1)
            {   /*
                  +---+
                  | * |
                  | * |
                  |   |
                  |***|
                  +---+
                */
                r2c = trova_singolo_in_riga(cc1 + 1, cc2 - 1, cr1);
                r2r2 = confine_inf(cr1 + 1, cr2 - 1);
                if (r2r2 == cr2  - 1)
                    r2r2++;
                mreport(cr2, cc1, cr2, cc2, cr1, r2c, r2r2, r2c);
            }
            else
            {   /*
                  +----+
                  |   *|
                  |** *|
                  |   *|
                  +----+
                */
                r1r = trova_singolo_in_colonna(cr1 + 1, cr2 - 1, cc1);
                r1c2 = confine_dx(cc1 + 1, cc2 - 1);
                if (r1c2 == cc2 - 1)
                    r1c2++;
                mreport(r1r, cc1, r1r, r1c2, cr1, cc2, cr2, cc2);
            }
    }
}

/*****************************************************************************/

int
main(void)
{   N = gridsize();
    confini();
    forma();
    risolvi();
    return 0;
}