Sprites Splitting with GLPK

/////// DEFINES //////////////
struct Sprite
{
    int type;
    int x,y;
    inline int sx() const
    {
        return ((type>>2)&3)+1;
    }
    inline int sy() const
    {
        return (type&3)+1;
    }
    int tc()
    {
        return sx()*sy();
    }
};

typedef std::vector<Sprite> SpriteList;

#define SIZE_X 400
#define SIZE_Y 400
#define CENTER_X (SIZE_X/2)
#define CENTER_Y (SIZE_Y/2)
unsigned char BMP[SIZE_X+32][SIZE_Y+32]; // FILL BMP YOURSELF
char S[SIZE_X/8+4][SIZE_Y/8+4];
bool N[0x10][SIZE_X/8][SIZE_Y/8];

////// ALGORITHM /////////////
int min = 100000, // min tiles init
    mx, // x shift to achieve min tiles
    my; // y shift to achieve min tiles

for (int sx=0; sx<8; ++sx) // brute x shift
    for (int sy=0; sy<8; ++sy) // brute y shift
    {
        int c = 0; // tiles count for this shift
        for (int x=sx; x<SIZE_X; x+=8) // brute x coord of tile
            for (int y=sy; y<SIZE_Y; y+=8) // brute y coord of tile
            {
                bool was = false; // was = tile not empty
                for (int i=0; i<8 && (!was); ++i)
                    for (int j=0; j<8 && (!was); ++j)
                        if (BMP[x+i][y+j])
                            was = true; // tile not empty!
                if (was)
                    ++c; // increment tiles count
            }
        if (c < min) // relax
        {
            min = c;
            mx = sx;
            my = sy;
        }
    }

memset(S, 0, sizeof(S)); // clear map: S[i][j] = not empty tile[i][j]?

for (int x=mx; x<SIZE_X; x+=8) // brute x coord of tile
    for (int y=my; y<SIZE_Y; y+=8) // brute y coord of tile
    {
        bool was = false; // was = tile not empty?
        for (int i=0; i<8 && (!was); ++i)
            for (int j=0; j<8 && (!was); ++j)
                if (BMP[x+i][y+j])
                    was = true; // tile not empty!
        S[(x-mx)/8][(y-my)/8]=was; // tile[i][j] not empty!
    }

FILE *f = fopen("tmtmp.gmpl", "w+"); // create temp gmpl file

memset(N, 0, sizeof(N)); // N[type][x][y] = need of var_type_x_y
for (int x=0; x<SIZE_X/8; ++x)
    for (int y=0; y<SIZE_Y/8; ++y)
    {
        Sprite s;   // dummy sprite object,
                    // only for calculating sprite size from sprite type
        for (s.type = 0; s.type < 0x10; ++s.type)
        {
            bool was = false; // was = sprite x,size_x,y,size_y not empty
            for(int i=0; i<s.sx(); ++i) // calculate "was"
                for (int j=0; j<s.sy(); ++j)
                    was |= S[x+i][y+j];
            N[s.type][x][y] = was; // need of var_type_x_y.
            if (was)
                fprintf(f,"var x%d_%d_%d, binary;\n",s.type,x,y); // define var in gmpl
        }
    }

// write function to minimize.
fprintf(f,"minimize obj: ");
{
bool was = false; // was operand before?
for (int x=0; x<SIZE_X/8; ++x)
    for (int y=0; y<SIZE_Y/8; ++y)
    {
        Sprite s;   // dummy sprite object,
                    // only for calculating sprite size from sprite type
        for (s.type = 0; s.type < 0x10; ++s.type)
        {
            if (!N[s.type][x][y])
                continue;
            if (!was) // if not was operand before - just space
                fprintf(f," ");
            else
                fprintf(f," + ");
            fprintf(f,"x%d_%d_%d*%d",s.type,x,y,s.tc()*200+1);
            was = true;
        }
    }
}
fprintf(f,";\n");

// write optimizing bounds (conditions)
int stc=0;
for (int y=0; y<SIZE_Y/8; ++y)
    for (int x=0; x<SIZE_X/8; ++x)
    {
        if (S[x][y]) // if tile x,y used
        {
            fprintf(f,"s.t. c%d: ", ++stc); // define new condition
            bool was = false; // was first operand?
            Sprite s;   // dummy sprite object,
                        // only for calculating sprite size from sprite type
            for (s.type = 0; s.type<0x10; ++s.type) // brute sprite type
            {
                // brute sprites which can contain tile x,y
                for (int i=x-s.sx()+1; i<=x; ++i)
                    for (int j=y-s.sy()+1; j<=y; ++j)
                    {
                        if (i<0||j<0)
                            continue;
                        if (was) // if was first operand, write +
                            fprintf(f," + ");
                        fprintf(f,"x%d_%d_%d",s.type,i,j);
                        was = true;
                    }
            }
            fprintf(f," >= 1;\n"); // tile x,y contains in one or more sprites
        }
    }

fprintf(f,"solve;\nend;\n"); // end of gmpl file

fclose(f);
printf("%%%d\n",min); // write min tiles that can achieve if all sprites size = 1

SpriteList res1;
char line[100];

// run glpsol
system("glpk\\glpsol.exe -o qwqwe.txt -m tmtmp.gmpl >nul");

// read output
f = fopen("qwqwe.txt","r");
for(;!feof(f);)
{
    if (!fgets(line,100,f))
        break; // end of file
    int n = strlen(line);
    if (n<8)
        continue; // skip not needed lines
    if (line[7]!='x')
        continue; // skip not needed lines
    Sprite s;
    int w; // w = use of sprite
    sscanf(line+7,"x%d_%d_%d * %d",&s.type,&s.x,&s.y,&w);
    if (w) // if used
        res1.push_back(s); // add sprite
}
fclose(f);