#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAXLEN 128

static int memicmp (const char *s, const char *t, int n) {
	int r = 0;
	while (n-- > 0 && (r = toupper (*s++) - toupper (*t++)) == 0);
	return (r);
	}

static int purify (double *x, double *y, int n);

main (int argc, char *argv[]) {
	int i,j,k,m,n;
	int nl,np;
	FILE *in;
	char input_file[MAXLEN];
	char string[MAXLEN],*s;
	double *x,*y;

	if (argc > 1) {
		strcpy (input_file,argv[1]);
		if (in = fopen (input_file,"r")) {
			k = 0;
			while (fgets (string,MAXLEN,in)) {
				if (s = strrchr (string,'\n')) *s = 0;
				if (memicmp (string,"REGION",6) == 0) {
					puts (string);
					if (sscanf (string+6,"%d",&nl) == 1) {
						k++;
						fprintf (stderr,"Region %3d has %3d lines\n",k,nl);
						m = 0;
						for (i=0; i < nl; i++) {
							fgets (string,MAXLEN,in);
							if (sscanf (string,"%d",&np) == 1) {
								m++;
								fprintf (stderr,"  line %3d has %4d points ... ",m,np);
								if (!(x = (double *) malloc (np * sizeof (double)))) {
									fprintf (stderr,"Error: could not allocate point array\n");
									exit (1);
									}
								if (!(y = (double *) malloc (np * sizeof (double)))) {
									fprintf (stderr,"Error: could not allocate point array\n");
									exit (1);
									}
								for (j=0; j < np; j++) {
									fgets (string,MAXLEN,in);
									if (sscanf (string,"%lf%lf",&x[j],&y[j]) != 2) {
										fprintf (stderr,"Error: two doubles expected in \"%s\"\n",string);
										exit (1);
										}
									}
								n = purify (x,y,np);
								fprintf (stderr," %3d points eliminated\n",np - n);
								printf ("%5d\n",n);
								for (j=0; j < n; j++) printf ("%10.6lf %10.6lf\n",x[j],y[j]);
								free (x);
								free (y);
								}
							else {
								fprintf (stderr,"Error: no number of points found in \"%s\"\n",string);
								exit (1);
								}
							}
						}
					else {
						fprintf (stderr,"Error: no number of lines found in \"%s\"\n",string);
						exit (1);
						}
					}
				else
					if (memicmp (string,"PLINE",5) == 0) {
						if (sscanf (string+5,"%d",&np) == 1) {
							fprintf (stderr,"  pline has %4d points ... ",np);
							if (!(x = (double *) malloc (np * sizeof (double)))) {
								fprintf (stderr,"Error: could not allocate point array\n");
								exit (1);
								}
							if (!(y = (double *) malloc (np * sizeof (double)))) {
								fprintf (stderr,"Error: could not allocate point array\n");
								exit (1);
								}
							for (j=0; j < np; j++) {
								fgets (string,MAXLEN,in);
								if (sscanf (string,"%lf%lf",&x[j],&y[j]) != 2) {
									fprintf (stderr,"Error: two doubles expected in \"%s\"\n",string);
									exit (1);
									}
								}
							n = purify (x,y,np);
							fprintf (stderr," %3d points eliminated\n",np - n);
							printf ("PLINE %4d\n",n);
							for (j=0; j < n; j++) printf ("%10.6lf %10.6lf\n",x[j],y[j]);
							free (x);
							free (y);
							}
						else {
							fprintf (stderr,"Error: no number of points found in \"%s\"\n",string);
							exit (1);
							}
						}
					else
						puts (string);
				}
			fclose (in);
			}
		else {
			fprintf (stderr,"Error: could not open input file %s\n",input_file);
			exit (1);
			}
		}
	else {
		fprintf (stderr,"Usage: %s infile\n",argv[0]);
		exit (1);
		}
	}

static int purify (double *x, double *y, int n) {
	int i,j,k,m;
	int *q;
	double ax,ay,bx,by,a,b,*t;
	double small,d2r;

	d2r = 3.141592653589793/180.0;

	small = cos(d2r * 2.0);

	if (!(q = (int *) malloc (n * sizeof (int)))) {
		fprintf (stderr,"Error: could not allocate q array\n");
		exit (1);
		}
	if (!(t = (double *) malloc (n * sizeof (double)))) {
		fprintf (stderr,"Error: could not allocate t array\n");
		exit (1);
		}

	for (i=0; i < n; i++) q[i] = 1;

	/*------------------------------------------------------------------*\
	 | Eliminate duplicate points										|
	\*------------------------------------------------------------------*/

	i = 0;
	for (j=1; j < n; j++)
		if (x[j] == x[i] && y[j] == y[i]) q[j] = 0;
		else i = j;

	i = 0;
	for (j=0; j < n; j++)
		if (q[j]) {
			x[i] = x[j];
			y[i] = y[j];
			q[i] = 1;
			i++;
			}
	n = i;

	/*------------------------------------------------------------------*\
	 | Eliminate intermediate points on lines							|
	\*------------------------------------------------------------------*/

	for (j=1; j < n-1; j++) {
		i = j-1;
		k = j+1;
		ax = x[j] - x[i];
		ay = y[j] - y[i];
		bx = x[k] - x[j];
		by = y[k] - y[j];
		a = ax*ax + ay*ay;
		b = bx*bx + by*by;
		t[j] = fabs(ax*bx + ay*by)/sqrt(a*b);
		if (t[j] > small) q[j] = 0;
		}

	i = 0;
	for (j=0; j < n; j++)
		if (q[j]) {
			x[i] = x[j];
			y[i] = y[j];
			q[i] = 1;
			i++;
			}
	n = i;

	/*------------------------------------------------------------------*\
	 | Return the number of points retained.							|
	\*------------------------------------------------------------------*/

	return (n);
	}