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

const int MAXDOTS = 150;
const int MAXLINES = 30;
//const bool DEBUGMODE = true;
const bool DEBUGMODE = false;
const bool ONLYDOIMPROVEMENTS = true;
//const bool ONLYDOIMPROVEMENTS = false;

const long REFMAX = 30000;
//const long REFCYCLE = 1;
const long REFCYCLE = REFMAX;
//const long REFCYCLE = 100;

// 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 rstm;
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 popping;
bool pushing;
bool finalcheck;

long refnum = 1;

bool firstrst[MAXDOTS];

void printstatus (void) ;

void getdots(void) {
  int firstrstnum;
  int scoretomatch;
  cin >> numdots;
  for (int i=0;i<numdots;i++) {
    cin >> dots[i];
  } 
  cin >> scoretomatch;
  rstm = scoretomatch * 2 + 1;
  cin >> firstrstnum;
  for (int i=0;i<numdots;i++) {
    firstrst[i] = false;
  }
  for (int i=0;i<firstrstnum;i++) {
    cin >> scoretomatch;
    firstrst[scoretomatch-1] = true;
  }
}

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 (rstm%2 == 0) 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";
  }
  cout << flush;
}

void addsegment(int linenum) {
  line* myline = &lines[linenum];
  int i;
//cout << "add " << linenum << "\n";
  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;
//cout << "remove " << linenum << "\n";
  // 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";
    }
  }
}

int checkre(int lastlinenum) {
  ratpoint sect;
  if (lines[0].intersect(lines[lastlinenum])) {
    ratpoint sect = lines[0].intersection(lines[lastlinenum]);
    if (lines[lastlinenum].between(
        lines[lastlinenum].point2(),
        lines[lastlinenum].point1(),
        sect) &&
        lines[0].between(
        lines[0].point1(),
        lines[0].point2(),
        sect)
       ) {
      endpoints[lastlinenum+1] = sect;
      endpoints[0] = sect;
      return 0;
    } else {
      return 1;
    }
  } else {
    return 1;
  } 
  // returns 0 if reentrant, 1 otherwise.
}

bool checksolution(int numline) {
  int myscore;
  if (numcovered == numdots) {
    myscore = numline*2 + checkre(numline-1);
    if (myscore < rstm) {
      rstm = myscore;
      printsol(numline);
      if (ONLYDOIMPROVEMENTS) {
        rstm--;
      }
      numsols = 1;
    } else if (myscore == rstm) {
      printsol(numline);
      numsols++;
      if (ONLYDOIMPROVEMENTS) {
        rstm--;
        numsols = 1;
      }
    }
    return true;
  } else {
    return false;
  }
}

bool contnue(int p1, int p2, line & myline) {
  ratpoint crosspt;

  if (p1==p2) return false;
  if (covered[p1] && covered[p2]) return false;
  if (curln == 0) {
    if (!firstrst[p1]) return false;
    for (int i=0;i<numdots;i++) 
      if (i!=p1 && i!=p2 && myline.hitpoint(dots[i])
        && myline.between(dots[i],dots[p1],dots[p2])) {            
          return false;
    }
    return true;
  }
  if (!myline.intersect(lines[curln-1])) return false;
  crosspt = myline.intersection(lines[curln-1]);
  if (lines[curln-1].side(crosspt) != 2) return false; 
  if (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;
  }
}

void dofinal(void) {
  assert(curln >= 2);
  endpoints[curln-1] = lines[curln-2].intersection(lines[curln-1]);
  endpoints[curln] = lines[curln-1].point2();
  for (int i=0;i<numdots;i++) 
    if (lines[curln-1].hitpoint(dots[i])
      && lines[curln-1].between(endpoints[curln],endpoints[curln-1],dots[i])) {
        endpoints[curln] = dots[i];
  }
  addsegment(curln-1);
  checksolution(curln);
  removesegment(curln-1);
  popping = true;
  finalcheck = false;
}

void increment(void) {
      lastpoint[curln]++;
      if (lastpoint[curln] == numdots) {
        firstpoint[curln]++;
        lastpoint[curln] = 0;
        if (firstpoint[curln] >= numdots) {
		  popping = true;
		}
      }
}

void dopop (void) {
  popping = false;
  curln--;
  if (curln > 0) {
    removesegment(curln-1);
  }
  increment();
}

void pushrecurse(void) {
  pushing = false;
  if (curln > rstm/2) {
    popping = true;
  } else if (checksolution(curln-1)) {
    dopop();
    popping = true;
  } else if (curln < rstm/2) {
    firstpoint[curln] = 0;
    lastpoint[curln] = 0;
  } else if (curln == rstm/2) {
    finalcheck = true;
  } 
}

void normrecurse(void) {
  line myline = line(dots[firstpoint[curln]],dots[lastpoint[curln]]);
  if (contnue(firstpoint[curln],lastpoint[curln],myline)) {
    lines[curln] = myline;
    if (curln == 0) {
      endpoints[curln] = myline.point1();
    } else {
      endpoints[curln] = myline.intersection(lines[curln-1]);
      addsegment(curln-1);
    }
    curln++;
    pushing = true;
  } 
  if (!pushing) {
    increment();
  }
}

void printstatus (void) {
  cout << "PS ";
  cout << rstm;
  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;
  curln = 0;
  popping = false;
  finalcheck = false;
  pushing = true;
  do {
/*    refnum++;
    if (refnum>=REFMAX) refnum = 0;
    if (refnum>=REFCYCLE) {
      printstatus();
      refnum = 0;
    }
*/

    if (finalcheck) {
      dofinal();
    } else if (popping) {
      dopop();
    } else if (pushing) {
      pushrecurse();
    } else {
      normrecurse();
    }
  } while ((curln != 0) || (firstpoint[0] != numdots));
  cout << "\n" << numsols << " solutions found.\n";
}