#include <stdio.h>
/* #include <stdlib.h> */

/*@
  terminates \false;
  assigns \nothing;
  ensures \false;
*/

void exit(int status);


#define true 1
#define false 0

static char pathdata[] = "style=\"fill:none;stroke:#000000;stroke-width:1px;stroke-opacity:1\"";


/* %define DEBUG 1 */

struct dart {
  int index, next0,  next1, prev1, x, y;
};

#define array_size 1000
static struct dart map[array_size];
static int bound = 0;
static int outer_edge = 0;

/* First section: reading in data */

int read_dart (int i) {
  int the_index, the_next0, the_next1, the_prev1, the_x, the_y;
  int success;
  success = scanf("%d %d %d %d %d %d", &the_index, &the_next0, &the_next1, &the_prev1, &the_x, &the_y);
  if (6 == success) {
    map[i].index = the_index;
    map[i].next0 = the_next0;
    map[i].next1 = the_next1;
    map[i].prev1 = the_prev1;
    map[i].x = the_x;
    map[i].y = the_y;
    return true;
  } else {
    return false;
  }
}

static int det_debug = 0;

int det3(int a, int b, int c, int d, int e, int f, int g, int h, int i) {
  int value = a * e * i + d * h * c + g * b * f -
          a * f * h - b * d * i - c * e * g;
  if (0 == value) {
    det_debug = 0;
    printf("%% computed a zero determinant\n%d %d %d\n%d %d %d\n%d %d %d\n",
	   a, b, c, d, e, f, g, h, i);
  }
  return value;
}

int find_outer_edge() {
  int i, j, k, det;
  for(i = 0; i < bound; i++) {
    j = next2(i);
    k = next2(j);

    det = det3(map[i].x, map[i].y, 1,
	       map[j].x, map[j].y, 1, 
	       map[k].x, map[k].y, 1);
    printf("%% debug find_outer_edge %d %d %d %d\n", i, j, k, det);
    if (det < 0) {
      return i;
    }
  }

  printf("This should never happen: no outer edge\n");
  exit(-1);
}

void read_darts () {
  int escape = false;
  for(bound = 0; true != escape; ) {
    if(true == read_dart(bound)) {
      bound++;
    } else {
      escape = true;
    };
  }
  printf("%% debug read_darts %d\n", bound);
  outer_edge = find_outer_edge();
}

/* Second section: checking consistency */

int next2(int i) {
  return (map[map[i].prev1].next0);
}

int prev2(int i) {
  return (map[map[i].next0].next1);
}

void ccw(int i) {
  int x1, y1, x2, y2, x3, y3, det;
  if(next2(next2(next2(i))) == i) {
    x1 = map[i].x;
    y1 = map[i].y;
    x2 = map[next2(i)].x;
    y2 = map[next2(i)].y;
    x3 = map[next2(next2(i))].x;
    y3 = map[next2(next2(i))].y;

    det = det3(x1, y1, 1, x2, y2, 1, x3, y3, 1);

    if(det <= 0) {
      printf("%% darts %d (%d, %d), %d (%d, %d), %d (%d, %d), %s (%d)\n",
	     i, map[i].x, map[i].y, next2(i), map[next2(i)].x,
	     map[next2(i)].y, next2(next2(i)), map[next2(next2(i))].x,
	     map[next2(next2(i))].y, "are not an oriented triangle", det);
    }
  }
}

void check_map() {
  int i;

  for(i = 0; i < bound; i++) {
    if (map[i].index != i) {
      printf("%% wrong index for dart %d : %d\n", i, map[i].index);
    }
    if (map[map[i].next0].next0 != i) {
      printf("%% wrong involution at level 0 for dart %d\n", i);
    }
    if (map[map[i].next1].prev1 != i) {
      printf("%% wrong inverse at level 1 for dart %d\n", i);
    }
    if (next2(next2(next2(i))) != i) {
      printf("%% dart %d not in a triangle\n", i);
    }
    ccw(i);
  }
}

/* Third section: reporting. */

void display_map() {
  int i, j;
  printf("<svg width=\"700\" height=\"1000\">\n");
  printf("<g id=\"layer1\">\n");

  for(i = 0; i < bound; i++) {
    j = map[i].next0;

    if(j > i) {
      printf("<path d=\"m %d,%d l %d,%d\" %s/>\n",
	     map[i].x, map[i].y, map[j].x, map[j].y, pathdata);
    }
  }
  printf("</g>\n</svg>\n");
}

void display_map_ps() {
  int i, j;
  printf("%%!PS\nnewpath\n");

  for(i = 0; i < bound; i++) {
    j = map[i].next0;

    if(j > i) {
      printf("%d %d moveto %d %d lineto\n",
	     10*map[i].x, 10*map[i].y, 10*map[j].x, 10*map[j].y);
    }
  }
  printf("stroke\nshowpage\n");
}

void dump_map () {
  int i;
  printf("%% %d darts at dumping time\n", bound);
  for(i = 0; i < bound; i++) {
    printf("%% %d %d %d %d %d %d\n",
	  map[i].index,
	  map[i].next0,
	  map[i].next1,
	  map[i].prev1,
	  map[i].x,
	  map[i].y);
  }
  printf("%% outer edge %d\n", outer_edge);
}

/* Fourth section: finding and correcting edges that violate the Delaunay
   condition. */
int illegal (int i) {
  int x1, y1, x2, y2, x3, y3, x4, y4, det;
#ifdef DEBUG
  int b, c, d;
  b = map[i].next0;
  c = next2(map[i].next0);
  d = next2(i);

  if((i == b) || (i == c) || (i == d) || (b == c) || (b == d) || (c == d)) {
    printf("%% testing edge legality in a wrong situation %d %d %d %d\n",
	   i, b, c, d);
  }
#endif
  x1 = map[i].x;
  y1 = map[i].y;
  x2 = map[map[i].next0].x;
  y2 = map[map[i].next0].y;
  x3 = map[next2(map[i].next0)].x;
  y3 = map[next2(map[i].next0)].y;
  x4 = map[next2(i)].x;
  y4 = map[next2(i)].y;

  det_debug = 1;

  det = det3(x1, y1, x1 * x1 + y1 * y1, x2, y2, x2 * x2 + y2 * y2, x3, y3, x3 * x3 + y3 * y3) +
    det3(x1, y1, x1 * x1 + y1 * y1, x3, y3, x3 * x3 + y3 * y3, x4, y4, x4 * x4 + y4 * y4) -
   det3(x1, y1, x1 * x1 + y1 * y1, x2, y2, x2 * x2 + y2 * y2, x4, y4, x4 * x4 + y4 * y4) -
    det3(x2, y2, x2 * x2 + y2 * y2, x3, y3, x3 * x3 + y3 * y3, x4, y4, x4 * x4 + y4 * y4);

  if((0 == det_debug) && (0 == det)) {
    printf("%% detected problem in illegal for dart %d\n", i);
  }

  if(det > 0) {
    return true;
  } else {
    return false;
  }
}

void unhook(int i) {
  int j, k;

  j = map[i].next1;
  k = map[i].prev1;

#ifdef DEBUG
  printf("detaching dart %d, relinking %d to %d\n", i, k, j);
#endif

  map[j].prev1 = k;
  map[k].next1 = j;

  map[i].next1 = i;
  map[i].prev1 = i;
}

void attach(int i, int j) {
  int k;

  k = map[i].prev1;

#ifdef DEBUG
  printf("attaching dart %d between %d and %d\n", j, k, i);
#endif

  map[j].next1 = i;
  map[i].prev1 = j;
  map[k].next1 = j;
  map[j].prev1 = k;

  map[j].x = map[i].x;
  map[j].y = map[i].y;
}

static int buffer;

int find_illegal() {
  int i, j;

  for(i = 0; i < bound; i++) {
    j = map[i].next0;

    if((next2(next2(next2(i))) == i) &&
       (next2(next2(next2(j))) == j)){
      if(illegal(i)) {
	buffer = i;
	return true;
      }
    }
  }
  return false;
}

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

  j = map[i].next0;
  k = next2(i);
  l = next2(j);

  unhook(i);
  unhook(j);
  attach(k, i);
  attach(l, j);
}

void mkdelaunay() {
  dump_map();
  while (find_illegal()) {
#ifdef DEBUG
    printf("flipping %d\n", buffer);
#endif
    flip(buffer);
  }
  dump_map();
}

/* Fifth section: adding a point  */

int add_dart(int x, int y) {
  int i;

  if(bound < array_size) {
    i = bound;
    map[i].index = i;
    map[i].next0 = i;
    map[i].next1 = i;
    map[i].prev1 = i;
    map[i].x = x;
    map[i].y = y;
    bound++;
    return i;
  } else {
    printf("array capacity exceeded\n");
    exit (-1);
  }
}

void add_point_triangle(int x, int y, int j) {
  int k, l, a, b, c, d, e, f;

  a = add_dart(x, y);
  b = add_dart(x, y);
  c = add_dart(x, y);
  k = next2(j);
  l = next2(k);
  d = add_dart(map[j].x, map[j].y);
  attach(j, d);
  e = add_dart(map[k].x, map[k].y);
  attach(k, e);
  f = add_dart(map[l].x, map[l].y);
  attach(l, f);
  map[b].prev1 = a;
  map[c].prev1 = b;
  map[a].prev1 = c;
  map[b].next1 = c;
  map[c].next1 = a;
  map[a].next1 = b;
  map[a].next0 = d;
  map[b].next0 = e;
  map[c].next0 = f;
  map[d].next0 = a;
  map[e].next0 = b;
  map[f].next0 = c;
  
}

int add_point_out (int x, int y) {

  int j, k, a0, a, b, det, found, stop;

  j = outer_edge;
  k = next2(j);
  found = false;

  while((k != outer_edge) && (found != true)) {
    k = next2(j);
    det = det3(map[j].x, map[j].y, 1, map[k].x, map[k].y, 1, x, y, 1);
    if(det > 0) {
      found = true;
    } else {
      j = k;
    }
  }
  if(true == found) {
    printf("%% found red point (%d, %d)\n", map[j].x, map[j].y);
    stop = false;
    while(stop != true) {
      k = prev2(j);
      det = det3(map[k].x, map[k].y, 1, map[j].x, map[j].y, 1, x, y, 1);
      if(det <= 0) {
	stop = true;
      } else {
	j = k;
      }
    }
    printf("%% first red point (%d, %d)\n", map[j].x, map[j].y);
    stop = false;
    a0 = add_dart(x, y);
    outer_edge = a0;
    b = add_dart(map[j].x, map[j].y);
    map[a0].next0 = b;
    map[b].next0 = a0;
    printf("%% first edge between (%d, %d) and (%d, %d)\n", 
	   map[a0].x, map[a0].y, map[b].x, map[b].y);
    while(stop != true) {
      k = next2(j);
      attach(j, b);
      det = det3(map[j].x, map[j].y, 1, map[k].x, map[k].y, 1, x, y, 1);
      if(det > 0) {
	a = add_dart(x, y);
	attach(a0, a);
	b = add_dart(map[k].x, map[k].y);
	map[a].next0 = b;
	map[b].next0 = a;
	printf("%% next edge between (%d, %d) and (%d, %d)\n", 
	   map[a].x, map[a].y, map[b].x, map[b].y);
	j = k;
      } else if(det = 0) {
	printf("%% new point is aligned with existing (%d, %d)\n", x, y);
	exit (-1);
      }else {
	stop = true;
      }
    }
  }
  return found;
}

void add_point(int x, int y) {
  int found, i, j, k, det;

  printf("%% enter add_point (%d, %d)\n", x, y);

  if(0 == bound) {
    add_dart(x, y);
  } else if(1 == bound) {
    add_dart(x, y);
    map[0].next0 = 1;
    map[1].next0 = 0;
  } else {
    found = add_point_out(x, y);
    if (true == found) {printf("%% add_point_out did it\n");}
    dump_map();
    if(true != found) {
      i = map[outer_edge].next0;

      found = false;
      while(true != found) {
	printf("%% looking for triangle currently at %d\n", i);
	j = next2(i);
	k = next2(j);
	det = det3(map[i].x, map[i].y, 1,
		   map[j].x, map[j].y, 1,
		   x, y, 1);
	if(det > 0) {
	  det = det3(map[j].x, map[j].y, 1,
		     map[k].x, map[k].y, 1,
		     x, y, 1);
	  if(det > 0) {
	    det = det3(map[k].x, map[k].y, 1,
		       map[i].x, map[i].y, 1,
		       x, y, 1);
	    if(det > 0) {
	      found = true;
	    } else if (0 == det) { 
	      printf("%% new point is aligned with existing ones (%d, %d)\n",
		 x, y);
	      exit(-1);
	    } else {
	      i = map[i].next0;
	    }
	  } else if (0 == det) {
	      printf("%% new point is aligned with existing ones (%d, %d)\n",
		 x, y);
	      exit(-1);
	  } else {
	    i = map[k].next0;
	  }
	} else if (0 == det) {
	  printf("%% new point is aligned with existing ones (%d, %d)\n",
		 x, y);
	  exit(-1);
	} else {
	  i = map[j].next0;
	}
      }
      printf("%% adding (%d, %d) inside (%d, %d)(%d, %d)(%d, %d)\n",
	     x, y, map[i].x, map[i].y, map[next2(i)].x, map[next2(i)].y,
	     map[next2(next2(i))].x, map[next2(next2(i))].y);
      add_point_triangle(x, y, i);
    }
    mkdelaunay();
  }
}

void read_points () {
  int escape = false;
  int x, y, success;

  while(true != escape) {
    success = scanf("%d %d", &x, &y);
    if(2 == success) {
      add_point(x, y);
    } else {
      escape = true;
    }
  }
}

int main() {
  printf("%%!PS\n");
  /*
  read_darts();
#ifdef DEBUG
  printf("%% %d darts\n", bound);
#endif
  mkdelaunay();
  add_point_triangle(120, 160, 5);
  printf("%% %d darts after adding a point\n", bound);
  mkdelaunay();
  add_point_out(20, 210);
  dump_map();
  mkdelaunay();
#ifdef DEBUG
  check_map();
#endif
  */
  read_points();
  display_map_ps();
  return 0;
}