#include <iostream> 
#include <fstream>
#include <list> 
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <cstring> //strcmp

using std::cout;
using std::endl;
using std::istream;
using std::ostream;
using std::ifstream;
using std::list;
using std::vector;
using std::set;
using std::map;
using std::swap;
using std::pair;

const int fieldSize = 100;
bool verbose;

struct Point
{
  int x, y;
  Point(int x_ = 0, int y_ = 0): x(x_), y(y_) 
  {}
};

struct Rect
{
  Point topLeft, bottomRight;
  bool contains(const Point& p)
  {
    return ( p.x >= topLeft.x     ) && 
           ( p.y >= topLeft.y     ) &&
           ( p.x <  bottomRight.x ) && 
           ( p.y <  bottomRight.y );
  }
};

struct NailPlace : Point
{
  set<  Rect * > papers;
  NailPlace(int x, int y): Point (x, y), isNailed(false)
  {}
  bool isNailed;
};

istream& operator >> (istream& is, Point& p);
istream& operator >> (istream& is, Rect& r);
ostream& operator << (ostream& os, const Rect& rect);
ostream& operator << (ostream& os, const NailPlace& nailPlace);
vector< Rect > *readFile(const char fileName[]);

int main(int argc, char *argv[])
{
  verbose = ( argc > 1 ) && ( strcmp( argv[ 1 ], "-v") == 0 );
  
  cout << "Reading file..." << endl;
  
  vector< Rect > &rects = *readFile( "points.txt" );
  if ( ( rects.empty() ) )
  {
    cout << "Error reading file" << endl;
    delete &rects;
    return -1;
  }
  
  cout << "Creating potential list..." << endl;
  
  // 1. Складаємо список місць для цвяхів. 
  list< NailPlace > potential;
  for( int x = 0; x < fieldSize; ++x )
    for( int y = 0; y < fieldSize; ++y )
    {
      //Для кожної клітинки визначити множину аркушів,
      NailPlace place(x, y);
      for( auto &rect: rects)
      {
        if( rect.contains( place ) )
        {
          // які на ній лежать.  
          place.papers.insert( &rect );
        }
      }
      if( verbose && !place.papers.empty() )
        cout << "Gathering papers: " << place << endl;
      for (auto nailPlace = potential.begin(); ( !place.papers.empty() )&& ( nailPlace != potential.end() ); ++nailPlace )
      {
        //2. Якщо ця множина є підмножиною множини, що вже є в списку, то ігноруємо її, інакше додаємо. 
        if( includes( nailPlace->papers.begin(), nailPlace->papers.end(), 
                      place.     papers.begin(), place.     papers.end() ) ) 
                        place.papers.clear();
        //Якщо в списку були підмножини доданої множини, видаляємо їх.         
        else if (includes( place.     papers.begin(), place.     papers.end(),
                           nailPlace->papers.begin(), nailPlace->papers.end() ) )
                             nailPlace = potential.erase( nailPlace );
      }
      if( !place.papers.empty() )
        potential.push_back( place );
    }
  if( verbose )
  {
    cout << "Potential list:" << endl; 
    for (auto &nailPlace : potential)
      cout << "Place:" << nailPlace << endl; 
  }
  //3. Шукаємо аркуші, що є членами рівно 
  bool change;
  do
  {
    map < Rect *, pair <unsigned int,  NailPlace *>  > rectCount;
    for( auto &nailPlace : potential )
      if( !nailPlace.isNailed )
        for( auto &rect : nailPlace.papers )
        {
          ++rectCount[ rect ].first;
          rectCount[ rect ].second = &nailPlace;
        }
    
    change=false;
    //однієї множини зі списку. 
    
    for( auto rect = rects.begin(); rect != rects.end(); ++rect )
      if( rectCount[ &*rect ].first == 1 )
      {
        //Прибиваємо.
        rectCount[ &*rect ].second->isNailed = true;
      }

/* ToDo:
4. Ті аркуші, що лишилися, будуть утворювати один чи декілька циклів. Перебираємо варіанти їх розірвання - скажімо, рекурсивною процедурою.
Це все можна і через графи описати, так навіть правильніше. Але мороки для початківця забагато.
*/    
    
  }while(change);
  cout << "Solution:" << endl; 
  for (auto &nailPlace : potential)
    if( nailPlace.isNailed )
      cout << "Place:" << nailPlace << endl; 
  delete &rects;
  return 0; 
}

istream& operator >> (istream& is, Point& p)
{
  return is >> p.x >> p.y;
}

istream& operator >> (istream& is, Rect& r)
{
  is >> r.topLeft >> r.bottomRight;
  if( r.topLeft.x > r.bottomRight.x)
    swap(r.topLeft.x, r.bottomRight.x);
  if( r.topLeft.y > r.bottomRight.y)
    swap(r.topLeft.y, r.bottomRight.y);
  return is;
}

ostream& operator << (ostream& os, const Rect& rect)
{
  return os << "("       << rect.topLeft.x     << ", " << rect.topLeft.y     
            << ")-(" << rect.bottomRight.x << ", " << rect.bottomRight.y
            << ")";
  
}

ostream& operator << (ostream& os, const NailPlace& nailPlace)
{
  os << "(" << nailPlace.x << ".5, " << nailPlace.y << ".5): ";
  for( auto &rect : nailPlace.papers)
    os << *rect << ", ";
  return os; 
}

vector< Rect > *readFile(const char fileName[])
{
  ifstream dataFile( fileName );
  auto rects = new vector< Rect >;
  if( !dataFile )
  {
    cout<<"Failed to open file!" << endl;
  }
  else
  {
    int line, n;
    dataFile>>n;
    for( line = 2; dataFile && ( line <= n + 1 ); ++line )
    {
      Rect rect;
      dataFile >> rect;
      rects->push_back( rect );
      if( verbose )    
        cout << rect << endl;
    }
    if( !dataFile )
    {
      cout<<"Failed to read file, error on line " << line << endl;
      rects->clear();
      return rects;
    } 
  }
  return rects;
}

Reading file...
(1, 2)-(4, 3)
(3, 2)-(4, 5)
(3, 4)-(4, 7)
(1, 6)-(4, 7)
(3, 4)-(6, 5)
(5, 4)-(8, 5)
Creating potential list...
Gathering papers: (1.5, 2.5): (1, 2)-(4, 3),
Gathering papers: (1.5, 6.5): (1, 6)-(4, 7),
Gathering papers: (2.5, 2.5): (1, 2)-(4, 3),
Gathering papers: (2.5, 6.5): (1, 6)-(4, 7),
Gathering papers: (3.5, 2.5): (1, 2)-(4, 3), (3, 2)-(4, 5),
Gathering papers: (3.5, 3.5): (3, 2)-(4, 5),
Gathering papers: (3.5, 4.5): (3, 2)-(4, 5), (3, 4)-(4, 7), (3, 4)-(6, 5),
Gathering papers: (3.5, 5.5): (3, 4)-(4, 7),
Gathering papers: (3.5, 6.5): (3, 4)-(4, 7), (1, 6)-(4, 7),
Gathering papers: (4.5, 4.5): (3, 4)-(6, 5),
Gathering papers: (5.5, 4.5): (3, 4)-(6, 5), (5, 4)-(8, 5),
Gathering papers: (6.5, 4.5): (5, 4)-(8, 5),
Gathering papers: (7.5, 4.5): (5, 4)-(8, 5),
Potential list:
Place:(3.5, 2.5): (1, 2)-(4, 3), (3, 2)-(4, 5),
Place:(3.5, 4.5): (3, 2)-(4, 5), (3, 4)-(4, 7), (3, 4)-(6, 5),
Place:(3.5, 6.5): (3, 4)-(4, 7), (1, 6)-(4, 7),
Place:(5.5, 4.5): (3, 4)-(6, 5), (5, 4)-(8, 5),
Solution:
Place:(3.5, 2.5): (1, 2)-(4, 3), (3, 2)-(4, 5),
Place:(3.5, 6.5): (3, 4)-(4, 7), (1, 6)-(4, 7),
Place:(5.5, 4.5): (3, 4)-(6, 5), (5, 4)-(8, 5),