#include <iostream.h>
#include <assert.h>
#include "lineseg.h"

const int MAXDOTS = 150;
const int MAXLINES = 30;

int numdots;
ratpoint dots[MAXDOTS];
line lines[MAXLINES];
ray rays[MAXLINES];
lineseg segs[MAXLINES];
int covered[MAXDOTS];
int numcovered = 0;
int rstm; // The "score" to beat or match.
 // 6 = 3 lines, reentrant
 // 7 = 3 lines, not reentrant
 // 8 = 4 lines, reentrant, etc.

bool firstrst[MAXDOTS];  // restricted first choices.

int numsols = 0;

// stack space variables
int curlevel = 0;
int firstpoint[MAXLINES];
int lastpoint[MAXLINES];

void printrentsol (void) {
  cout << "Solution found; reentrant " << curlevel+1 << " lines\n";
  for (int i=0;i<=curlevel;i++) {
    cout << segs[i] << "\n  hits:";
    for (int j=0;j<numdots;j++) if (segs[i].hitpoint(dots[j]))
      cout << dots[j];
    cout << "\n";
  }
  cout << "\n";
}

void printnormsol (void) {
  cout << "Solution found; not reentrant " << curlevel+1 << " lines\n";
  for (int i=0;i<curlevel;i++) {
    cout << segs[i] << "\n  hits:";
    for (int j=0;j<numdots;j++) if (segs[i].hitpoint(dots[j]))
      cout << dots[j];
    cout << "\n";
  }
  cout << rays[curlevel] << "\n  hits:";
  for (int j=0;j<numdots;j++) if (rays[curlevel].hitpoint(dots[j]))
    cout << dots[j];
  cout << "\n\n";
}

void debugg (void) {
  cout << "level " << curlevel << ": ";
  for (int i=0;i<=curlevel;i++)
    cout << "(" << firstpoint[i] << "," << lastpoint[i] << ")";
  cout << "\n Points covered by first " << curlevel-1 << " segs: "
       << numcovered << "\n";
  for (int i=0;i<numdots;i++)
    cout << covered[i] << " ";
  cout << "\n";
}

void getdots(void) {  
  int scoretomatch;  int temp;
  int firstrstnum;
  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++) {  
    covered[i] = -1;
    firstrst[i] = false;
  }
  for (int i=0;i<firstrstnum;i++) {
    cin >> temp;
    firstrst[temp-1] = true;
  } 
}

void create(void) {
  // adds a new ray at the end of the curve.
  // if this isn't the first ray, must check the previous points,
  // as the last increment didn't do it.
  firstpoint[curlevel] = 0;
  lastpoint[curlevel] = 0;
}

bool overflow(void) {
  // sees if the last increment made an invalid ray
  return (firstpoint[curlevel] >= numdots);
}

void increment(void) {
  // goes to the next ray .. does not recalculate as ray might be invalid.
  if (lastpoint[curlevel]==numdots-1) {
    firstpoint[curlevel]++;
    lastpoint[curlevel] = 0;
  } else 
    lastpoint[curlevel]++;
}

bool invalid(void) {
  // sees if the ray was redundant and should be pruned. 
  // precondition:  curlevel==0 || rays[curlevel-1] is defined
  int fp,lp;
  lineseg fplp;
  fp = firstpoint[curlevel];
  lp = lastpoint[curlevel];

  // can't define something by the same point
  if (fp==lp) return(true);

  if (curlevel==0) {
     // can't have the first ray come from a disallowed point
     if (!firstrst[firstpoint[curlevel]]) return(true);

     fplp = lineseg(dots[fp],dots[lp]);

     // must have the "simplest" line segment, no dots in between.
     for (int lcv=0;lcv<numdots;lcv++)
      if ((lcv!=fp) && (lcv!=lp) && fplp.hitpoint(dots[lcv])) 
       return(true);

     // all other first-level ones are fine
     return(false);
  } else {
     ray tempray,tempray2;
     // not first level

     // Must intersect previous ray AFTER second point
     // and before own first point
     tempray = ray(dots[lastpoint[curlevel-1]],dots[firstpoint[curlevel-1]]);
     tempray.reverse();
     tempray2 = ray(dots[fp],dots[lp]);
     tempray2.reverse();
     if (!tempray2.intersect(tempray)) return(true);
     
     fplp = lineseg(tempray2.intersection(tempray),dots[lp]);     

     // must have the "simplest" line segment, no dots in between.
     for (int lcv=0;lcv<numdots;lcv++)
      if ((lcv!=fp) && (lcv!=lp) && fplp.hitpoint(dots[lcv])) 
       return(true);

     // all other rays are okay
     return(false);
  }
}

bool issolution(void) {
  // assumes ray is valid, and sees if it hits rest of the dots needed.
  // if so, prints the solution.
  // preconditions -- 
  //  numcovered, covered is okay up to curlevel-2
  //  segs is okay up to curlevel-2
  //  rays is okay up to curlevel-1

  // if our solution isn't reentrant there's no point to continuing.
  
  ratpoint temp;
  int pointshit=0;

  if (curlevel==0) {
    rays[0]=ray(dots[firstpoint[0]],dots[lastpoint[0]]);
  } else {
    line templine = line(dots[firstpoint[curlevel]],dots[lastpoint[curlevel]]);
    temp = rays[curlevel-1].intersection(templine);
    segs[curlevel-1]=lineseg(rays[curlevel-1].startpt(),temp);
    rays[curlevel]=ray(temp,dots[lastpoint[curlevel]]);
    for(int i=0;i<numdots;i++) if (covered[i]==(-1))
      if (segs[curlevel-1].hitpoint(dots[i]) 
        ||rays[curlevel].hitpoint(dots[i]))
        pointshit++;
  }
  if (pointshit+numcovered==numdots) {
    // we have a solution
      
    // but is it reentrant?
    int metric;
    ray endray;
    ray startray;
    
    endray = rays[curlevel];
    for (int i=0;i<numdots;i++) 
      if ((covered[i] == (-1))
        && (endray.startpt() != dots[i]) 
        && endray.hitpoint(dots[i])
        ) {
      endray = ray(dots[i],endray.startpt());
      endray.reverse();
    }
    startray = rays[0];
    startray.reverse();
    
    if (endray.intersect(startray)) {
      // we're reentrant!
      metric = curlevel*2+2;
      ratpoint endpt = endray.intersection(startray);
      segs[curlevel] = lineseg(segs[curlevel].pt1(),endpt);
      printrentsol();
      numsols++;
    } else {
      // we're not reentrant
      metric = curlevel*2+3;
      if (metric<=rstm) printnormsol();
      numsols++;
    }
    if (metric<rstm) {
      rstm = metric;
      numsols = 1;
    }
    return (true);
  } else {
    return(false);
  }
}

void calclastlevel(void) {
  // adds the line segment  [curlevel-1] to the database.
  if (curlevel!=0)
  for (int i=0;i<numdots;i++) 
    if ((covered[i]==(-1)) && segs[curlevel-1].hitpoint(dots[i])) {
      covered[i] = curlevel-1;
      numcovered++;
  }
}

void uncalclastlevel(void) {
  // removes line segment [curlevel-1] from database.
  if (curlevel!=0)
  for (int i=0;i<numdots;i++) if (covered[i]==curlevel-1) {
    numcovered--;
    covered[i] = (-1);
  }
}

void main(void) {
  getdots();
  curlevel = 0;
  create();
  while (curlevel >= 0) {
    if ((curlevel*2+2>rstm) || overflow()) {
      curlevel--;
      uncalclastlevel();
      increment();
    } else if (invalid() || issolution()) {
      increment();
    } else {
      calclastlevel();
      curlevel++;
      create();
//debugg();
    }
  }
  cout << "Number of Solutions: " << numsols << "\n";
}