/* Tutorial on Reverse Search */
/* Section 7: Euclidean tree generation  R*/

/* input: n (number of edges) followed by x_0 y_0 ... x_n y_n */

#include <stdio.h>
#define TRUE 1
#define FALSE 0

typedef int tree[100];
typedef int point[2];

/* global variables */
int n;                  /* number of edges in tree */
int depth=0;            /* depth of current node in reverse search tree */
point p[100];           /* coordinates of nodes in tree                 */


/* additional geometric procedures */

int areasign( point a, point b, point c )
/* returns +1,0,-1 if abc is left, straight, right turn */
{
  long sign;
  sign = ( b[0] - a[0] ) * ( c[1] - a[1] ) -
            ( c[0] - a[0] ) * ( b[1] - a[1] );
  if      ( sign  >  0 ) return  1;
  else if ( sign   <  0 ) return -1;
  return  0;
}

int between( point a, point b, point c )
/* returns TRUE iff point c lies on the open segement ab */
/* for collinear a,b,c                                   */
{
   if ( a[0] != b[0] )  /* not vertical */
      return ((a[0] < c[0]) && (c[0] < b[0])) ||
             ((a[0] > c[0]) && (c[0] > b[0]));
   return    ((a[1] < c[1]) && (c[1] < b[1])) ||
             ((a[1] > c[1]) && (c[1] > b[1]));
}

int cross ( point a, point b, point c, point d)
/* returns TRUE if segment ab properly intersects segment cd */
{
  int sabc,sabd,scda,scdb;

  sabc=areasign(a,b,c);
  if (sabc==0 && between(a,b,c)) return TRUE;
  sabd=areasign(a,b,d);
  if ( sabd==0 && between(a,b,d)) return TRUE;
  scda=areasign(c,d,a);
  if ( scda==0 && between(c,d,a)) return TRUE;
  scdb=areasign(c,d,b);
  if ( scdb==0 && between(c,d,b)) return TRUE;
  if (( sabc * sabd < 0 ) && ( scda * scdb < 0)  )
      return TRUE;
  return FALSE;
}

int crossedge (tree v, int i, int j)
/* return TRUE if new edge from i to j intersects anyone else */
{
 int k;
 for(k=1;k<=n;k++)
     if(cross(p[i],p[j],p[k],p[v[k]]))
        return TRUE;
  return FALSE;
}

void getpointdata()
{
  int i,j,k,l;

  for (i=0;i<=n;i++)
    scanf ("%d %d", &p[i][0],&p[i][1]);
  printf("points: %d %d",p[0][0],p[0][1]);
  for (i=1;i<=n;i++)
    printf(", %d %d",p[i][0],p[i][1]);
/* report any crossing edges */
  printf("\ncrossings (if any):");
  for(i=0;i<=n-2;i++)
   for(j=i+1;j<=n;j++)
    for(k=i;k<=n-1;k++)
     for(l=k+1;l<=n;l++)
    {
       if(!(k==i && l<j)&&cross(p[i],p[j],p[k],p[l]))
             printf("\n%d %d   %d %d ",i,j,k,l);
     }
}

/* From here same as tree.c except where markded with /***/

void output (tree v)
/* output parent of node i, i=1..n */
{
  int i;
  for (i = 1; i <= n; i++)
    printf (" %d", v[i]);
  printf ("   depth=%d",depth);
}

void next(tree v, int* r, int* s)
/* increment j and possibly i skipping any node whose parent is not root */
{
 int i=(*r), j=(*s);
 j++;
 if ( i == j) j++;
 if (j > n || v[i] != 0)
    { do i++;
        while ( i <=n && v[i] != 0 );
      j=1;
    }
 (*r)=i; (*s)=j;
}

void copy (tree w, tree v)
{
  int i;
  for (i = 1; i <= n; i++)
    w[i] = v[i];
}

int equal (tree w, tree v)
{
  int i;
  for (i = 1; i <= n; i++)
    if (w[i] != v[i])
      return FALSE;
  return TRUE;
}

int root (tree v)
{
  int i;
  for (i = 1; i <= n; i++)
    if (v[i] != 0)
      return FALSE;
  return TRUE;
}

int Adj (tree v, int i, int j)          /*   adjacency oracle */
{                                       /* i is child of root */
 int p;
 p=v[j];                         /* see if root ancestor of j */
 while ( p != 0 && p != i ) p=v[p];     
 if ( (p==i) || crossedge(v,i,j) ) return FALSE;           /***/
 v[i]=j;
 return TRUE;                   /* j becomes parent of i */
}

void f (tree v, int* i, int* j)                 /* local search function */
{                        /* set i,j s.t v=Adj(f(v),i,j)  then set v=f(v) */
  int k=1;
  while ( k <= n && ( v[k] ==  0 || crossedge(v,0,k)) ) k++;          /***/
  if (k <= n)                                   /* v is not root of tree */
   { (*i)=k; (*j)=v[k];
     v[k]=0;
   }
}

int reverse (tree v, int i, int j)
{
  tree w;
  copy (w, v);
  if( !Adj (w,i,j)) return FALSE;                                        /***/
  f (w,&i,&j);     /* i, j get changed, but are not returned to reversearch */
  return equal (v, w);
}


int reversesearch (tree v)
{
  int i=1, j=1, count=1;
  output (v);
  while ( i <= n )
    {
      do next(v,&i,&j);
          while (i <= n && !reverse (v,i,j));
      if (i <= n)
        {
          Adj (v,i,j);
          count++; depth++;
          printf("\n");
          output(v);
          i=1; j=1;
        }
      else if (!root(v))
         {
           f(v,&i,&j);
           depth--;
          }
    }
  return count;
}


int main ()			/*  reverse search for euclidean trees  */
{
  tree v;        /* v[i] is parent of i in tree rooted at 0 */
  int i, count;
  scanf ("%d", &n);

  getpointdata();
  for (i = 1; i <= n; i++) v[i]=0;
  printf("\neuclidean spanning trees:\n");
  count = reversesearch (v);
  printf ("\nnumber of trees=%d\n", count);
  return 0;
}