#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <errno.h>
#include <stdlib.h>
#include <strings.h>
#if 0
#include <unistd.h>
#include <stdarg.h>
#endif

extern const char *__progname;

typedef struct picfile PICFILE;
typedef struct point POINT;
typedef struct datapt DATAPT;
typedef struct pt2 PT2;

struct pt2 {
  PT2 *link;
  POINT *p;
  DATAPT *a;
  DATAPT *b;
  } ;

struct picfile {
  PICFILE *link;
  char *name;
  int serial;
  DATAPT *pts;
  } ;

struct point {
  POINT *link;
  char *name;
  int serial;
  DATAPT *pts;
  } ;

struct datapt {
  DATAPT *flink;
  DATAPT *plink;
  PICFILE *pf;
  POINT *pt;
  int x;
  int y;
  } ;

static PICFILE *picfiles;
static int picfile_serial;
static POINT *points;
static int point_serial;

static const char *datafile;
static FILE *datafp;
static PICFILE *pfa;
static PICFILE *pfb;
static PT2 *pt2s;

#define cisspace(x) isspace((unsigned char)(x))

static int id2(int, int, int, int) __attribute__((__const__));
static inline int id2(int x1, int y1, int x2, int y2)
{
 return(((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)));
}

#define DATA_CB_PROTO char *, char *, int, int, int, int
#define DATA_CB_ARGS \
	char *ptname __attribute__((__unused__)),	\
	char *filename __attribute__((__unused__)),	\
	int xpt __attribute__((__unused__)),		\
	int ypt __attribute__((__unused__)),		\
	int xlbl __attribute__((__unused__)),		\
	int ylbl __attribute__((__unused__))
static void read_data(void (*cb)(DATA_CB_PROTO))
{
 static char *b = 0;
 static int a = 0;
 int n;
 int c;
 int lno;

 void savec(int ch)
  { if (n >= a) b = realloc(b,a=n+8);
    b[n++] = ch;
  }

 void haveline(void)
  { char *s0[6];
    char *s1[6];
    long int v[4];
    int i;
    char *s;
    lno ++;
    s = b;
    for (i=0;i<6;i++)
     { while (*s && cisspace(*s)) s ++;
       if (! *s)
	{ fprintf(stderr,"%s: \"%s\", line %d: ignoring unparseable line `%s'\n",__progname,datafile,lno,b);
	  return;
	}
       s0[i] = s;
       while (*s && !cisspace(*s)) s ++;
       s1[i] = s;
     }
    while (*s && cisspace(*s)) s ++;
    if (*s)
     { fprintf(stderr,"%s: \"%s\", line %d: ignoring junk at end of line `%s'\n",__progname,datafile,lno,b);
     }
    for (i=0;i<6;i++) *s1[i] = '\0';
    for (i=0;i<4;i++)
     { v[i] = strtol(s0[i+2],&s,0);
       if ((s == s0[i+2]) || *s)
	{ fprintf(stderr,"%s: \"%s\", line %d: bad number `%s', ignoring line\n",__progname,datafile,lno,s0[i+2]);
	  return;
	}
       if ((v[i] < 0) || (v[i] != (int)v[i]))
	{ fprintf(stderr,"%s: \"%s\", line %d: number `%s' out of range, ignoring line\n",__progname,datafile,lno,s0[i+2]);
	  return;
	}
     }
    (*cb)(s0[0],s0[1],v[0],v[1],v[2],v[3]);
  }

 rewind(datafp);
 n = 0;
 lno = 0;
 while <"readloop"> (1)
  { c = getc(datafp);
    switch (c)
     { case EOF:
	  if (ferror(datafp))
	   { fprintf(stderr,"%s: read error on %s\n",__progname,datafile);
	     exit(1);
	   }
	  if (n)
	   { savec('\0');
	     haveline();
	   }
	  break <"readloop">;
	  break;
       case '\n':
	  savec('\0');
	  haveline();
	  n = 0;
	  break;
       default:
	  savec(c);
	  break;
     }
  }
}

static PICFILE *find_picfile(const char *name)
{
 PICFILE **pfp;
 PICFILE *pf;

 pfp = &picfiles;
 while ((pf = *pfp))
  { if (!strcmp(pf->name,name))
     { if (pfp != &picfiles)
	{ *pfp = pf->link;
	  pf->link = picfiles;
	  picfiles = pf;
	}
       return(pf);
     }
    pfp = &pf->link;
  }
 pf = malloc(sizeof(PICFILE));
 pf->name = strdup(name);
 pf->serial = picfile_serial ++;
 pf->pts = 0;
 pf->link = picfiles;
 picfiles = pf;
 return(pf);
}

static POINT *find_point(const char *name)
{
 POINT *pt;

 for (pt=points;pt;pt=pt->link)
  { if (!strcmp(pt->name,name)) return(pt);
  }
 pt = malloc(sizeof(POINT));
 pt->name = strdup(name);
 pt->serial = point_serial ++;
 pt->pts = 0;
 pt->link = points;
 points = pt;
 return(pt);
}

static void save_pts(DATA_CB_ARGS)
{
 PICFILE *pf;
 POINT *pt;
 DATAPT *d;

 pf = find_picfile(filename);
 pt = find_point(ptname);
 d = malloc(sizeof(DATAPT));
 d->x = xpt;
 d->y = ypt;
 d->pf = pf;
 d->pt = pt;
 d->flink = pf->pts;
 pf->pts = d;
 d->plink = pt->pts;
 pt->pts = d;
}

static int cmp_datapt_picfile(DATAPT *a, DATAPT *b)
{
 return(a->pf->serial-b->pf->serial);
}

static int cmp_datapt_point(DATAPT *a, DATAPT *b)
{
 return(a->pt->serial-b->pt->serial);
}

static DATAPT *sort_datapts(
	DATAPT *list,
	DATAPT *(*linkfn)(DATAPT *),
	DATAPT **(*linkptr)(DATAPT *),
	int (*cmp)(DATAPT *, DATAPT *) )
{
 DATAPT *a;
 DATAPT *b;
 DATAPT *t;
 DATAPT **lp;

 if (list && (*linkfn)(list))
  { a = 0;
    b = 0;
    while (list)
     { t = list;
       lp = (*linkptr)(t);
       list = *lp;
       *lp = a;
       a = b;
       b = t;
     }
    lp = &list;
    while (a || b)
     { if (a && (!b || ((*cmp)(a,b) < 0)))
	{ t = a;
	  a = (*linkfn)(a);
	}
       else
	{ t = b;
	  b = (*linkfn)(b);
	}
       *lp = t;
       lp = (*linkptr)(t);
     }
    *lp = 0;
  }
 return(list);
}

static DATAPT *link_pf(DATAPT *d)
{
 return(d->flink);
}

static DATAPT *link_pt(DATAPT *d)
{
 return(d->plink);
}

static DATAPT **linkptr_pf(DATAPT *d)
{
 return(&d->flink);
}

static DATAPT **linkptr_pt(DATAPT *d)
{
 return(&d->plink);
}

static void sort_lists(void)
{
 PICFILE *pf;
 POINT *pt;

 for (pf=picfiles;pf;pf=pf->link)
  { pf->pts = sort_datapts(pf->pts,&link_pf,&linkptr_pf,&cmp_datapt_point);
  }
 for (pt=points;pt;pt=pt->link)
  { pt->pts = sort_datapts(pt->pts,&link_pt,&linkptr_pt,&cmp_datapt_picfile);
  }
}

static void setup_data(void)
{
 datafp = fopen(datafile,"r");
 if (! datafp)
  { fprintf(stderr,"%s: %s: %s\n",__progname,datafile,strerror(errno));
    exit(1);
  }
 picfiles = 0;
 picfile_serial = 0;
 points = 0;
 point_serial = 0;
 read_data(&save_pts);
 sort_lists();
}

static void handleargs(int ac, char **av)
{
 int skip;
 int errs;

 skip = 0;
 errs = 0;
 for (ac--,av++;ac;ac--,av++)
  { if (skip > 0)
     { skip --;
       continue;
     }
    if (**av != '-')
     { if (! datafile)
	{ datafile = *av;
	}
       else
	{ fprintf(stderr,"%s: stray argument `%s'\n",__progname,*av);
	  errs = 1;
	}
       continue;
     }
    if (0)
     {
needarg:;
       fprintf(stderr,"%s: %s needs a following argument\n",__progname,*av);
       errs = 1;
       continue;
     }
#define WANTARG() do { if (++skip >= ac) goto needarg; } while (0)
    if (!strcmp(*av,"-data"))
     { WANTARG();
       datafile = av[skip];
       continue;
     }
#undef WANTARG
    fprintf(stderr,"%s: unrecognized option `%s'\n",__progname,*av);
    errs = 1;
  }
 if (errs) exit(1);
}

static void scan_common_pts(PICFILE *pfa, PICFILE *pfb, void (*fn)(DATAPT *, DATAPT *))
{
 DATAPT *a;
 DATAPT *b;

 a = pfa->pts;
 b = pfb->pts;
 while (a && b)
  { if (a->pt->serial == b->pt->serial)
     { (*fn)(a,b);
       a = a->flink;
       b = b->flink;
     }
    else if (a->pt->serial < b->pt->serial)
     { a = a->flink;
     }
    else
     { b = b->flink;
     }
  }
}

static void pick_pfs(void)
{
 PICFILE *a;
 PICFILE *b;
 int n;
 int curn;

 curn = -1;
 for (a=picfiles;a;a=a->link)
  { for (b=a->link;b;b=b->link)
     { void inc_n(DATAPT *a __attribute__((__unused__)), DATAPT *b __attribute__((__unused__)))
	{ n ++;
	}
       n = 0;
       scan_common_pts(a,b,&inc_n);
       if (n > curn)
	{ curn = n;
	  pfa = a;
	  pfb = b;
	}
     }
  }
 if (curn <= 0)
  { fprintf(stderr,"%s: can't find any overlap\n",__progname);
    exit(1);
  }
 if (curn < 3)
  { fprintf(stderr,"%s: insufficient overlap\n",__progname);
    exit(1);
  }
 printf("Initial pair: %s and %s, overlap %d\n",pfa->name,pfb->name,curn);
}

static void pick_points(void)
{
 PT2 *p;
 PT2 *q;
 int da;
 int db;
 int d;
 PT2 *bestp;
 PT2 *bestq;
 int bestd;

 void gen_pt2s(DATAPT *a, DATAPT *b)
  { PT2 *p;
    if (a->pt != b->pt) abort();
    p = malloc(sizeof(PT2));
    p->p = a->pt;
    p->a = a;
    p->b = b;
    p->link = pt2s;
    pt2s = p;
  }

 pt2s = 0;
 bestd = -1;
 scan_common_pts(pfa,pfb,&gen_pt2s);
 for (p=pt2s;p;p=p->link)
  { for (q=p->link;q;q=q->link)
     { da = id2(p->a->x,p->a->y,q->a->x,q->a->y);
       db = id2(p->b->x,p->b->y,q->b->x,q->b->y);
       d = (da < db) ? da : db;
       if (d > bestd)
	{ bestd = d;
	  bestp = p;
	  bestq = q;
	}
     }
  }
 if (bestd < 0)
  { fprintf(stderr,"%s: can't find best starting pair\n",__progname);
    exit(1);
  }
 printf("bestd = %g, points %s and %s\n",sqrt(bestd),bestp->p->name,bestq->p->name);
}

int main(int, char **);
int main(int ac, char **av)
{
 handleargs(ac,av);
 setup_data();
 pick_pfs();
 pick_points();
 return(0);
}