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

#define STREETLIM 10000
#define PROPLIM 1000
#define REALCOORDLIM 10000

typedef struct {double x, y;} point;
typedef struct {point p1,p2;} line;

int intersect(point *p,line l1, line l2)
{ double A,B,C,D,E,F;
  A = l1.p1.x * l1.p2.y - l1.p1.y * l1.p2.x;
  B = l2.p1.x * l2.p2.y - l2.p1.y * l2.p2.x;
  C = l1.p1.x - l1.p2.x;
  D = l2.p1.x - l2.p2.x;
  E = l1.p1.y - l1.p2.y;
  F = l2.p1.y - l2.p2.y;
  p->x = (A*D - C*B) / (C*F - E*D);
  p->y = (A*F - E*B) / (C*F - D*E);
  if(isnan(p->x) || isinf(p->x) || isnan(p->y) || isinf(p->y))
    return 0;
  return 1;
}

void printpoint(point *p)
{
  printf("(%lf,%lf)",p->x,p->y);
}
void printline(line *l)
{
  printf("[");
  printpoint(&(l->p1));
  printf(",");
  printpoint(&(l->p2));
  printf("]");
}

int liesbetween(point p, line l)
{
  double dxc,dyc,dxl,dyl,cross;
  dxc = p.x - l.p1.x;
  dyc = p.y - l.p1.y;
  dxl = l.p2.x - l.p1.x;
  dyl = l.p2.y - l.p1.y;
  // we know p is on the line, just check endpoints
  /* cross = dxc * dyl - dyc * dxl; */
  /* if (cross != 0) */
  /*   return 0; */
  if (fabs(dxl) >= fabs(dyl))
   return dxl > 0 ? l.p1.x<=p.x && p.x<=l.p2.x : l.p2.x<=p.x && p.x<=l.p1.x;
  else
    return dyl > 0 ? l.p1.y<=p.y && p.y<=l.p2.y : l.p2.y<=p.y && p.y<=l.p1.y;
}

int lieson(point p, line l)
{
  double dxc,dyc,dxl,dyl,cross;
  dxc = p.x - l.p1.x;
  dyc = p.y - l.p1.y;
  dxl = l.p2.x - l.p1.x;
  dyl = l.p2.y - l.p1.y;
  cross = dxc * dyl - dyc * dxl;
  if (fabs(cross) < 0.0000001)
    return 1;
  return 0;
}

int colinear(line l1,line l2)
{
  if(lieson(l1.p1,l2)&&lieson(l1.p2,l2))
    return 1;
  return 0;
}

int samepoint(point a, point b)
{
  if(a.x == b.x && a.y==b.y)
    return 1;
  return 0;
}


int main(int argc, char **argv)
{
  int Ns,s,Np,p,x,y;
  int grid = 1;
  int COORDLIM = REALCOORDLIM;
  line *streets;
  line *properties;
  int duplicate,i,reject;
  
  if(argc != 5)
    {
      fprintf(stderr,"Usage: %s num_streets num_tests maxcoord \"grid\"|\"random\"\n",argv[0]);
      exit(1);
    }
  
  srand(time(NULL));

  if(((Ns = atoi(argv[1])) > STREETLIM) || (Ns <0))
    {
      fprintf(stderr,"Number of streets must be between 0 and %d.\n",STREETLIM);
      exit(1);
    }

  if(((Np = atoi(argv[2])) > PROPLIM) || (Np <0))
    {
      fprintf(stderr,"Number of streets must be between 0 and %d.\n",PROPLIM);
      exit(2);
    }

  if(((COORDLIM = atoi(argv[3])) > REALCOORDLIM) || (Np <0))
    {
      fprintf(stderr,"Max coord must be between 0 and %d.\n",REALCOORDLIM);
      exit(3);
    }

  if(!strcmp(argv[4],"grid"))
    grid = 1;
  else
    if(!strcmp(argv[4],"random"))
      grid = 0;
    else
      {
	fprintf(stderr,"Must specify grid or random.\n",STREETLIM);
	exit(4);
      }

  streets = malloc(Ns*sizeof(line));
  properties = malloc(Np*sizeof(line));
  
  printf("%d\n",Ns);

  //  generate streets
  for(s = 0; s < Ns; s++)
    do
      {
	duplicate = 0;
	streets[s].p1.x = rand()%(COORDLIM+1);
	streets[s].p1.y = rand()%(COORDLIM+1);
	if(grid)
	  if(s&1)
	    {
	      streets[s].p2.x = streets[s].p1.x;
	      streets[s].p2.y = rand()%(COORDLIM+1);
	    }
	  else
	    {
	      streets[s].p2.y = streets[s].p1.y;
	      streets[s].p2.x = rand()%(COORDLIM+1);
	    }
	else 
	  {
	    streets[s].p2.x = rand()%(COORDLIM+1);
	    streets[s].p2.y = rand()%(COORDLIM+1);
	  }
	for(i=0;!duplicate && i<s;i++)
	  if(colinear(streets[i],streets[s]))
	    duplicate = 1;
      }
    while(duplicate);
  
  
  for(i = 0; i < Ns; i++)
    printf("%d %d %d %d\n",
	   (int)streets[i].p1.x,(int)streets[i].p1.y,
	   (int)streets[i].p2.x,(int)streets[i].p2.y);
  
  printf("%d\n",Np);
  
  for(p = 0; p < Np; p++)
    do {
      reject = 0;
      properties[p].p1.x = rand()%(COORDLIM+1);
      properties[p].p1.y = rand()%(COORDLIM+1);
      properties[p].p2.x = rand()%(COORDLIM+1);
      properties[p].p2.y = rand()%(COORDLIM+1);
      for(s=0;!reject && s<Ns;s++)
	{
	  if(lieson(properties[p].p1,streets[s]))
	    reject = 1;
	  if(lieson(properties[p].p2,streets[s]))
	    reject = 1;
	}
    } while(reject);
  
  for(i = 0; i < Np; i++)
    printf("%d %d %d %d\n",
	   (int)properties[i].p1.x,(int)properties[i].p1.y,
	   (int)properties[i].p2.x,(int)properties[i].p2.y);
  
  
  return 0;
}