#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using std::cout;
using std::endl;
using std::ios_base;
using std::ifstream;
using std::getline;
using std::vector;

struct      MyRect
{
    int     xTopLeft,
            yTopLeft,
            xBottomRight,
            yBottomRight;
};

vector<MyRect>    pointList;

const int   SIZE                 = 101;

bool    isEmptyRect(MyRect r)
{
    return ( (r.xBottomRight-r.xTopLeft) == SIZE ) && ( (r.yBottomRight-r.yTopLeft) == SIZE );
}

int         N,
            nails;

int         field[SIZE][SIZE];

bool    readData();
void    coverField();

bool    crossAreas(MyRect, MyRect);
int     findMax();
int     nailField();
MyRect  findFirstRect(int);

int main()
{
    N       = 0;
    nails   = 0;

    if( !readData() )
    {
        cout << "Cannot read data from file!" << endl;
        return 1;
    }

    while(!pointList.empty())
    {
        memset(field, 0, sizeof(field));
        coverField();
        nails += nailField();
    }

    cout << "Nails: " << nails << endl;

    return 0;
}

/* Find max-level of covering */
int     findMax()
{
    int     m = field[0][0];

    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            m = ( field[i][j] > m )? field[i][j] : m;

    return  m;
}

/* Find the first of the Max-covered squares */
MyRect  findFirstRect(int level)
{
    MyRect  r;
    int     x, y;       // top left

    for(y = 0; y < SIZE; y++)
        for(x = 0; x < SIZE; x++)
        {
            if(field[y][x] == level)  // top left corner
                goto TOP;
        }

TOP:
    int w = SIZE, h = SIZE;

    for(int jX = x; jX < SIZE; jX++)
        if(field[y][jX] != level)
        {
            w = jX;
            break;
        }

    for(int iX = x; iX < w; iX++)
        for(int jY = y; jY < SIZE; jY++)
            if(field[jY][iX] != level)
            {
                h = jY;
                goto BOTTOM;
            }
BOTTOM:
    r.xTopLeft = x;         r.yTopLeft = y;
    r.xBottomRight = w;    r.yBottomRight = h;

    return r;
}

/* Checking whether the Point and Square cross each other */
bool     crossAreas(MyRect p, MyRect s)
{
    return  ( p.xTopLeft <= s.xTopLeft )            &&
            ( p.xBottomRight >= s.xBottomRight)     &&
            ( p.yTopLeft <= s.yTopLeft )            &&
            ( p.yBottomRight >= s.yBottomRight)
            ;
}

/* Find the max-covered square, nail it - and log about it (by clearing pointList) */
int     nailField()
{
    if( !pointList.size() )         // No area to compare with the field
        return 0;

    int     level       = findMax();

    MyRect  area = findFirstRect(level);
    if( isEmptyRect(area) )
        return 0;

    vector<MyRect> newPoints;

    // Leave only not-crossed
    for(size_t i = 0; i < pointList.size(); i++)
        if( !crossAreas(pointList[i], area) )   // NOT crossed
            newPoints.push_back(pointList[i]);

    pointList.clear();
    pointList = newPoints;

    return 1;   // Nail!
}



bool    readData()
{
    ifstream    f;
    f.open("/work/test/schooltask/points.txt", ios_base::in);

    if(! f.is_open())
    {
        cout<<"Fail to open file!" << endl;
        return false;
    }

    char    str[20]     ={0};

    f.getline(str, 19, '\n');        // Read first line - 'N'

    if( !sscanf(str, "%d", &N) || N<1 || N>20 )
    {
        cout << "Invalid value of \'N\'!" << endl;
        f.close();
        return false;
    }

    for(int i = 1; i <= N && !f.eof(); i++)
    {
        memset(str, 0, 20);
        f.getline(str, 19, '\n');
        MyRect  r;
        if( sscanf(str, "%d;%d;%d;%d", &r.xTopLeft, &r.yTopLeft, &r.xBottomRight, &r.yBottomRight) != 4)
        {
            cout << "Row #" << i << " data is invalid." << endl;
            continue;
        }
        pointList.push_back(r);
    }

    cout << "Data has been loaded." << endl;

    f.close();
    return true;
}

void coverField()
{
    for( vector<MyRect>::iterator iter = pointList.begin(); iter != pointList.end(); iter++ )
    {
        for(int iX = (*iter).xTopLeft; iX < (*iter).xBottomRight; iX++)
            for(int jY = (*iter).yTopLeft; jY < (*iter).yBottomRight; jY++)
                field[jY][iX] ++;
    }
}

7
5;6;15;20
30;6;50;15
10;15;25;25
70;70;80;90
40;50;45;55
36;10;45;22
70;0;80;10