/* program: quadrate.c
   author: Werner Hoch <werner.ho@gmx.de>
   description:  search squares in a field of points
   the field in the file look like this
  |
 -+-----------> col
  | xxxxxxx         line, col --> (-row, col)
  | xxxxxxx
  | xx x xx
  | xx x xx
  | xx x xx
  | xxxxxxx
  | xxxxxxx
  |
  V row
*/

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

#define TOL 0.1

typedef struct point{
  double x,y;
  struct point * next;
} POINT;

POINT * head=NULL;

int
file_load(char * name) {
  FILE *f;
  int row=-1, col=1;
  int c;
  POINT *p;
  POINT * cursor=NULL;

  if ((f = fopen(name,"rt")) == NULL) {
    fprintf(stderr, "Error: Cannot open file: %s \n", name);
    return (0);
  }
  
  while ((c=fgetc(f)) != EOF) {
    switch (c) {
    case 'x':
    case 'X':
      p = malloc(sizeof(POINT));
      if (p==NULL)
	return 0;
      p->x = col;
      p->y = row;
      p->next=NULL;
      if (head == NULL) {
	head = p;
      } else {
	cursor->next=p;
      }
      cursor = p;
      col++;
      break;
    case ' ':
      col++;
      break;
    case '\n':
      row--;
      col=1;
      break;
    default:
      printf("d");
    }
  }
  return 1;
}

int
check(POINT * p1, POINT *p2, POINT *p3, POINT *p4) {
  double length, dx, dy, angle;

  dx=p2->x - p1->x;
  dy=p2->y - p1->y;
  length= sqrt(dx*dx + dy*dy);
  angle=atan2(dy,dx);

  p3->x=p2->x + length*cos(angle+M_PI_2);
  p3->y=p2->y + length*sin(angle+M_PI_2);
  p4->x=p3->x + length*cos(angle+M_PI);
  p4->y=p3->y + length*sin(angle+M_PI);

  if (has_point(p3, p1) && has_point(p4, p1)) 
    return 1;
  return 0;
}

int
has_point(POINT *p, POINT * cur) {
  for (; cur; cur=cur->next) {
    if (cur->x > (p->x-TOL) && cur->x < (p->x+TOL)
	&& cur->y > (p->y-TOL) && cur->y < (p->y+TOL))
      return 1;
  }
  return 0;
}

int
main (int argc, char *argv[]) {
  int size, row, col;
  int solutions=0;
  POINT *cur1, *cur2, p3, p4;

  if (argc < 2) {
    printf("Count the squares in the matrix\n");
    printf("  usage: %s [matrixfile]\n",argv[0]);
    return -1;
  }
  
  if (! file_load(argv[1]))
    return -1;

  for (cur1=head; cur1 != NULL; cur1=cur1->next) {
    for (cur2=cur1->next; cur2 != NULL; cur2=cur2->next) {
      if (check(cur1, cur2, &p3, &p4)) {
	solutions++;
	printf("(%.1f,%.1f), (%.1f,%.1f), (%.1f,%.1f), (%.1f,%.1f)",
	       cur1->x, cur1->y, cur2->x, cur2->y, p3.x, p3.y, p4.x, p4.y);
	printf("  solution %d\n", solutions);
      }
    }
  }
  return 0;
}