#include <conio.h>
#include <malloc.h>
#include <stdlib.h>
#include <graphics.h>
#include <stdio.h>
#define round(a) ((int)(a+0.5))
#define line(a,b,c,d) line(a,480-(b),c,480-(d))

int compare(const void *a,const void *b)
{
 return *(int *)a - *(int *)b;
}

void swap(int &x1,int &y1,int &x2,int &y2)
{
 int t;
 t=x1; x1=x2; x2=t;
 t=y1; y1=y2; y2=t;
}

struct xyz
{
int ymax;
double x;
double invsl;
struct xyz * next;
};
struct xyz * et[480]={0};
struct xyz * aet=0;

//just a debugging function
void printet()
{
int i=0;
struct xyz * trav;
printf("START : PrintET\n");
while(!et[i]) i++;

while(i<480)
{
trav=et[i];
if(trav) { printf("%d: ",i);
while(trav) { printf("ym:%d x:%lf 1/n:%lf >>>>",trav->ymax,trav->x,trav->invsl);
	      trav=trav->next;
	    }
	  printf("%%\n");
	 }
i++;
}
printf("END : PrintET");
}



void makeet(int x1,int y1,int x2,int y2)
{
 struct xyz * etn, *trav;
 if(y1==y2) return;
 etn=(struct xyz *)malloc(sizeof(xyz));

if(y1>y2) swap(x1,y1,x2,y2);

 etn->invsl=(1.0*x2-x1)/(y2-y1);
 etn->ymax=y2;
 etn->x=(double)x1;
 etn->next=0;

      if(!et[y1]) { et[y1]=etn; }
      else
	     { trav=et[y1];
	       while(trav->next!=NULL)
		trav=trav->next;
	       trav->next=etn;
	     }
}



main()
{

  int x[20],y[20],n,i,j,k,arr[20],gm,gd=DETECT;
  struct xyz * trav;


  printf("Enter the number of points:");
  scanf("%d",&n);
//n=3;

  printf("Enter the points:");
  for(i=0;i<n;i++)
   scanf("%d%d",&x[i],&y[i]);
/*
x[0]=100; y[0]=100;
x[1]=200; y[1]=200;
x[2]=100; y[2]=300;
*/

  initgraph(&gd,&gm,"c:\\tcpp30\\bgi");

  //draw the polygon
  for(i=0;i<n-1;i++)
   line(x[i],y[i],x[i+1],y[i+1]);
  line(x[n-1],y[n-1],x[0],y[0]);
  getch();

  //form the et
  for(i=0;i<n-1;i++)
   makeet(x[i],y[i],x[i+1],y[i+1]);
  makeet(x[n-1],y[n-1],x[0],y[0]);

//  printet();

  //goto first nonempty et bucket
  i=0;
  while(!et[i]) { i++; }

  //change the fillcolor to see some white left over at ymax
  setcolor(RED);


// START MAIN ALGO

while(1)
{
  //move et row into end of aet
  if(!aet)
  { aet=et[i];
  }
  else
  { trav=aet;
    while(trav->next!=NULL)
    {
      trav=trav->next;
    }
    trav->next=et[i];
    et[i]=0;
  }
  //move into arr the x's where i<ymax
  trav=aet; j=0;
  while(trav)
  { if(i<trav->ymax)
      arr[j++]=round(trav->x);
    trav=trav->next;
  }
  if(j==0) break; //end the algo

  //sort arr
  qsort(arr,j,sizeof(int),compare);


  //plot using pairs
  for(k=0;k+1<j;k+=2)
    line(arr[k],i,arr[k+1],i);

  //increment current scanline
  i++;

  //update aet
  trav=aet;
  while(trav)
  {
     trav->x+=trav->invsl;
     trav=trav->next;
  }
}


getch();
return 0;
}