#include <iostream.h>
#include <assert.h>
#include "line.h"
#include "ratpoint.h"
#include "rational.h"

const int MAXDOTS = 100;
const int MAXLINES = 20;
//const bool DEBUGMODE = true;
const bool DEBUGMODE = false;
const bool ONLYSHOWIMPROVEMENTS = true;
//const bool ONLYSHOWIMPROVEMENTS = false;

// Tries to solve dot problems by a brute-force algorithm.

// We'll assume that every line goes through at least two dots, at least
// one of which has not been already gone through.  

// Start with two dots, and draw a line through them.  The next line
// must go through two dots and intersect the previous line at a location
// outside of the two dots.

int numdots;
int bestlines;  // best solution known.  We will only print
   // a solution if we beat or equal this number.
bool reentrant;  // Is the best solution reentrant?  If it is,
  // don't print any non-reentrant solutions.
int numsols = 0;
ratpoint dots[MAXDOTS];
ratpoint endpoints[MAXLINES+1];
line lines[MAXLINES];
bool covers[MAXLINES][MAXDOTS];
   // true if that line covers that dot. 
bool covered[MAXDOTS];
int numcovered = 0;
   // so we won't have to scan through covers[] all the time.
bool celsewhere;

// stackspace variables
int firstpoint[MAXLINES+2];
int lastpoint[MAXLINES+2];
int curln;
bool spopping[MAXLINES];
bool popping;
bool pushing;
bool finalcheck;

void getdots(void) {
  cin >> numdots;
  for (int i=0;i<numdots;i++) {
    cin >> dots[i];
  } 
  cin >> bestlines;
}

void printdots(void) {
  cout << "numdots is " << numdots << "\n"; 
  for (int i=0;i<numdots;i++) {
    cout << "Dot " << i << " is " << (dots[i]) << "\n";
  } 
  cout << "numdots is " << numdots << "\n"; 
}

void printsol(const int numlines) {
  cout << "\nSolution found with " << numlines << " lines.\n";
  if (reentrant) cout << "This solution is reentrant.\n";
  for (int i=0;i<numlines;i++) {
    cout << "Line " << i+1 << " starts at ";
    cout << endpoints[i];
    cout << "\n  goes through ";
    for (int j=0;j<numdots;j++) if (covers[i][j])
      cout << dots[j] << " ";
    cout << "\n  and ends at ";
    cout << endpoints[i+1];
    cout << "\n";
  }
}

void addsegment(int linenum) {
  line* myline = &lines[linenum];
  int i;
  for (i=0;i<numdots;i++) { if((*myline).hitpoint(dots[i])) {
    if ((*myline).between(dots[i],endpoints[linenum],endpoints[linenum+1])) {
      covers[linenum][i] = true;
      if (!covered[i] && covers[linenum][i]) {
        covered[i] = true;
        numcovered++;
        if (DEBUGMODE) cout << "    Crosses new point " << dots[i] << "\n";
        if (DEBUGMODE) cout << "    " << numcovered << " points covered\n";
      }
    } else
      covers[linenum][i] = false;
    } else
      covers[linenum][i] = false;
  }
}

void removesegment (int linenum) {
  int j;
  // now undo all that stuff about covering.
  for (int i=0;i<numdots;i++) 
    if (covers[linenum][i]) {

    // we may have to remove it; does any other line cover it?
    celsewhere = false;

    j=0;
    while ((!celsewhere) && (j < linenum)) { 
      if (covers[j][i]) {
        celsewhere = true;
      }
      j++;
    }

    if (!celsewhere) {
      covered[i] = false;
      numcovered--;
      if (DEBUGMODE) cout << "    uncrosses point " << dots[i] << "\n";
      if (DEBUGMODE) cout << "    " << numcovered << " points covered\n";
    }
  }
}

bool checkre(int numlines) {
  ratpoint sect;
  if (lines[0].intersect(lines[numlines])) {
    ratpoint sect = lines[0].intersection(lines[numlines]);
    if (lines[numlines].between(
        lines[numlines].point2(),
        lines[numlines].point1(),
        sect) &&
        lines[0].between(
        lines[0].point1(),
        lines[0].point2(),
        sect)
       ) {
      endpoints[numlines-1] = sect;
      reentrant = true;
      return true;
    } else {
      return false;
    }
  } else {
    return false;
  } 
}

void checksolution(const int numlines) {
    if (numlines < bestlines) {
      bestlines = numlines;
      reentrant = checkre(numlines);
      printsol(numlines);
      cout << "This improves on the best solution.\n";
      numsols = 1;
    } else if (!reentrant) {
      if (checkre(numlines)) {
        printsol(numlines);
        numsols = 1;
      } else if (!ONLYSHOWIMPROVEMENTS) {
        printsol(numlines);
        numsols++;
      }
    } else if (!ONLYSHOWIMPROVEMENTS && checkre(numlines)) {
      printsol(numlines);
      numsols++;
    }
}

bool contnue(int p1, int p2, int numlines) {
      line myline = line(dots[p1],dots[p2]);
      ratpoint crosspt;
      if (numlines > 0) {
        if (myline.intersect(lines[numlines-1])) {
          crosspt = myline.intersection(lines[numlines-1]);
          if (lines[numlines-1].side(crosspt) != 2) { 
            return false;
          }
          if (contnue && (myline.side(crosspt) != 0)) {
            return false;
          }
          for (int i=0;i<numdots;i++) 
            if (i!=p1 && i!=p2 && myline.hitpoint(dots[i])
                   && myline.between(dots[i],crosspt,dots[p2])) {
            
            return false;
          }
        } else {
          return false;
        }
      }
}

void dofinal(void) {
  assert(curln >= 2);
  endpoints[curln-1] = lines[curln-2].intersection(lines[curln-1]);
  endpoints[curln] = lines[curln-1].point2();
  addsegment(curln-1);
  if (numcovered == numdots) 
    checksolution(curln);
  removesegment(curln-1);
  popping = true;
}

void pushrecurse(const int numlines) {
  pushing = false;
  if (numcovered == numdots) 
    checksolution(numlines-1);
  if (numlines > bestlines) {
    popping = true;
  } else if (numlines == bestlines) {
    finalcheck = true;
  } else /* if (numlines < bestlines) */ {
    firstpoint[numlines] = 0;
    lastpoint[numlines] = 0;
  }
}

void normrecurse(int numlines) {
  int p1 = firstpoint[numlines];
  int p2 = lastpoint[numlines];
  line myline = line(dots[p1],dots[p2]);
  pushing = false;
  if (p1 != p2) if (!covered[p1] || !covered[p2]) {
    if (contnue(p1,p2,numlines)) {
      lines[numlines] = myline;
      if (numlines == 0) {
        endpoints[numlines] = myline.point1();
      } else {
        endpoints[numlines] = myline.intersection(lines[numlines-1]);
        addsegment(numlines-1);
      }
      curln++;
      pushing = true;
    }
  } 
  if (!pushing) {
      lastpoint[numlines]++;
      if (lastpoint[numlines] == numdots) {
        firstpoint[numlines]++;
        lastpoint[numlines] = 0;
        if (firstpoint[numlines] == numdots) popping = true;
      }
  }
}

void printstatus (void) {
  cout << "PS ";
  cout << bestlines;
  cout << " " << curln;
  cout << " " << numcovered << " ";
  cout << (pushing? "T" : "F");
  cout << (popping? "T" : "F");
  cout << (finalcheck? "T" : "F") << " ";
  for (int i=0;i<=curln;i++) {
    cout << i ;
    cout << "(" << firstpoint[i] << "," << lastpoint[i] << ")";
  }
  cout << "\n";
}

void main (void) {
  getdots();
  assert(numdots > 1);
  numcovered = 0;
  for (int i=0;i<numdots;i++) covered[i] = false;
  for (int i=0;i<MAXLINES;i++) spopping[i] = false;
  curln = 0;
  popping = false;
  pushing = true;
  do {
    //printstatus();
    if (finalcheck) {
      dofinal();
      finalcheck = false;
    } else if (popping) {
      if (curln > 1) {
        removesegment(curln-2);
      }
      popping = false;
      curln--;
      lastpoint[curln]++;
      if (lastpoint[curln] == numdots) {
        firstpoint[curln]++;
        lastpoint[curln] = 0;
      }
      if (firstpoint[curln] >= numdots) {
        popping = true;
      }
    } else if (pushing) {
      pushrecurse(curln);
    } else {
      normrecurse(curln);
    }
  } while ((curln != 0) || (firstpoint[0] != numdots));
  cout << "\n" << numsols << " solutions found.\n";
}