/* PARR_max_con -- PARR: maximal connections   Copyright (C) 2015 Frans Faase

   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., 675 Mass Ave, Cambridge, MA 02139, USA.

GNU General Public License:
   http://www.iwriteiam.nl/GNU.txt

Details:
   http://www.iwriteiam.nl/D1510.html#6

*/

#include <stdio.h>

#define MAX_POINTS 1000

struct Config
{
    Config(int n_n, int n_m, int *n_corners, int n_added, Config *n_next)
      : n(n_n), m(n_m), added(n_added), next(n_next)
    {
        for (int i = 0; i < 4; i++)
            corners[i] = n_corners[i];
    }
    ~Config() { delete next; }
    bool equal(int n_n, int n_m, int *n_corners, int n_added)
    {
        if (n != n_n || m != n_m || added != n_added)
            return false;
        for (int i = 0; i < 4; i++)
            if (corners[i] != n_corners[i])
                return false;
        return true;
    }
    int n;
    int m;
    int corners[4];
    int added;
    Config *next;
};

struct {
    int lines;
    Config *configs;
} results[MAX_POINTS+1];

void add(int points, int lines, int n, int m, int *corners, int added)
{
    if (points > MAX_POINTS || results[points].lines > lines)
        return;
    if (results[points].lines < lines)
    {
        results[points].lines = lines;
        delete results[points].configs;
        results[points].configs = 0;
    }
    for (Config *config = results[points].configs; config != 0; config = config->next)
        if (config->equal(n, m, corners, added))
            return;
    results[points].configs = new Config(n, m, corners, added, results[points].configs);
}

int main(int argc, char *argv)
{
    for (int i = 0; i <= MAX_POINTS; i++)
    {
        results[i].lines = 0;
        results[i].configs = 0;
    }
    
    bool go = true;
    for (int n = 0; n < 400; n++)
    {
        go = false;
        //fprintf(stderr, "n=%d\n", n);
        int maxd = n/4;
        if (maxd < 3) maxd = 3;
        int m = n - maxd;
        if (m < 3) m = 3;
        for (; m <= n; m++)
        {
            //fprintf(stderr, " m=%d\n", m);
            int c1 = (m-1)/2 - 3;
            if (c1 < 1) c1 = 1;
            for (; c1 <= (m-1)/2; c1++)
            {
                int c2 = m-1 - c1;
                //fprintf(stderr, "  c1=%d, c2=%d\n", c1, c2);
                int points = m*n - c1*(c1+1) - c2*(c2+1);
                if (points <= MAX_POINTS)
                {
                    go = true;
                    int lines = 4*(m-1)*(n-1) + (m-1) + (n-1) - 2*(2*c1*(c1+1) - c1) - 2*(2*c2*(c2+1) - c2);
                    int c[4];
                    c[0] = c[1] = c1;
                    c[2] = c[3] = c2;
                    add(points, lines, n, m, &c[0], 0);
                    for (int c_m = c2; c_m > 0 && points <= MAX_POINTS; c_m--)
                        for (int i = 0; i < 4; i++)
                            if (c[i] == c_m)
                            {
                                int added = 1;
                                for (int j = 1; j <= c_m && points < MAX_POINTS; j++, added++)
                                {
                                    points++;
                                    lines += j == 1 ? 3 : 4;
                                    //if (((j > 1 && j >= c_m/2) || j == c_m) && added > 0)
                                    if (j >= c_m/2 && added > 0)
                                    {
                                        added -= c[i];
                                        c[i]--;
                                    }
                                    add(points, lines, n, m, &c[0], added);
                                }
                            }
                }
            }
        }
    }
    
    for (int i = 0; i < MAX_POINTS; i++)
        if (results[i].lines > 0)
        {
            printf("%4d: %4d (%d)",
                i,
                results[i].lines,
                results[i].lines - results[i-1].lines);
            for (Config *config = results[i].configs; config != 0; config = config->next)
            {
                printf(" = %dx%d-%d,%d,%d,%d",
                    config->n,
                    config->m,
                    config->corners[0],
                    config->corners[1],
                    config->corners[2],
                    config->corners[3]);
                if(config->added > 0)
                    printf("+%d", config->added);
                else if (config->added < 0)
                    printf("%d", config->added);
            }
            printf("\n");
        }

    return 0;
}