/*
 * 2D Geometric Predicates
 * 15-745:L3, Todd Phillips
 * Some basic 2d predicates for integer coordinate points
 */

void print_bool(int i) {}
void print_space(int i) {}
void print_newline(void) {}

// Basic 2D Point


struct Point2D {
  int x;
  int y;
};


// cross product
int cross(struct Point2D a, struct Point2D b)
{
  return ((a.x * b.y) - (a.y * b.x));
}

int dot(struct Point2D a, struct Point2D b)
{
  return ((a.x * b.x) + (a.y * b.y));
}

// negation
struct Point2D *minus(struct Point2D a)
{
  struct Point2D b;
  b.x = - a.x;
  b.y = - a.y;
  return &b;
}


// add two vectors                                               
struct Point2D *sum (struct Point2D a, struct Point2D b)
{
  static struct Point2D c;
  c.x = a.x + b.x;
  c.y = a.y + b.y; 
  return &c;     
}                                                       

// Is d in the circle through (a,b,c) ?
// This has a fair amount of subexpression redundancy
// Lots of negations
int incircle(struct Point2D a, struct Point2D b, struct Point2D c, struct Point2D d)
{
  struct Point2D *ad,*bd,*cd;
  int abdet,bcdet,cadet;
  int alift,blift,clift;

  ad = sum ( a, *minus(d));
  bd = sum ( b, *minus(d));
  cd = sum ( c, *minus(d));

  abdet = cross(*ad, *bd);
  bcdet = cross(*bd, *cd);
  cadet = cross(*cd, *ad);

  alift = dot(*ad, *ad);
  blift = dot(*bd, *bd);
  clift = dot(*cd, *cd);

  return (alift * bcdet + blift * cadet + clift * abdet >= 0);
}

void main(void) {
  struct Point2D a,b,c,d;
  int scale;
  int side;

  scale = 6;

  for ( a.x = 0; a.x < scale ; a.x += 1) 
    for ( b.x = 0; b.x < scale; b.x += 1) 
      for ( c.x = 0; c.x < scale; c.x += 1) 
	for ( d.x = 0; d.x < scale; d.x += 1) 
	  for ( a.y = 0; a.y < scale ; a.y += 1) 
	    for ( b.y = 0; b.y < scale; b.y += 1) 
	      for ( c.y = 0; c.y < scale; c.y += 1) 
		for ( d.y = 0; d.y < scale; d.y += 1) 
		  {
		    side = incircle(a,b,c,d);
		    print_bool(side);
		    print_space(2);
		  }
  print_newline();
}