const char * UsageLines [] = {
	"Usage: drawpolygons (width) (height)",
	"Reads corners of polygons in across, down coordinates, from standard input.",
	"Writes a ppm image of specified width and height to standard output.",
	"Each nonblank input line must begin with colors r g b followed",
	"by across,down for each corner (at least 3 corners to have any effect).",
	"The order is front-to-back, meaning a polygon will cover",
	"any polygon given in a later line.",
	"drawpolygon ignores anything after # to end-of-line.",
	"January 4, 2017.  Newest is at gopher -p users/julianbr sdf.org",
	};
const int NumUsageLines = sizeof (UsageLines)/sizeof (UsageLines [0] );


struct Polygon {
	int r, g, b;
	struct Corner {
		long int across, down;
		struct Corner * next;
		} * Corners;
	struct Polygon * next;
	};

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


#define BackgroundR 200
#define BackgroundG 200
#define BackgroundB 200


int ReadPolygon (struct Polygon * * PolygonPtr, int * EndOfInputPtr)
	{
	struct Polygon * Polygon;
	struct Corner * * CornerPtr, * Corners, * Corner;
	int ok, c, IsNegative;
	int r, g, b, across, down, Found, FoundB, FoundDown;

	ok = 1;
	c = getchar ();
	while (c == ' ')
		c = getchar ();
	Found = 0;
	Polygon = NULL;
	if (c != EOF && c != '\n' && c != '#') {
		Found = 1;
		PolygonPtr [0] = malloc (sizeof (PolygonPtr [0] [0] ) );
		Polygon = PolygonPtr [0];
		if (ok && Polygon == NULL) {
			fprintf (stderr, "***drawpolygons: Not enough memory");
			ok = 0;
			}
		}
	IsNegative = 0;
	if (c == '+')
		c = getchar ();
	else if (c == '-') {
		IsNegative = 1;
		c = getchar ();
		}
	r = 0;
	while (c >= '0' && c <= '9') {
		r = 10*r + (c - '0');
		c = getchar ();
		}
	if (IsNegative)
		r = - r;
	while (c == ' ')
		c = getchar ();
	IsNegative = 0;
	if (c == '+')
		c = getchar ();
	else if (c == '-') {
		IsNegative = 1;
		c = getchar ();
		}
	g = 0;
	while (c >= '0' && c <= '9') {
		g = 10*g + (c - '0');
		c = getchar ();
		}
	if (IsNegative)
		g = - g;
	while (c == ' ')
		c = getchar ();
	IsNegative = 0;
	if (c == '+')
		c = getchar ();
	else if (c == '-') {
		IsNegative = 1;
		c = getchar ();
		}
	FoundB = 0;
	b = 0;
	while (c >= '0' && c <= '9') {
		FoundB = 1;
		b = 10*b + (c - '0');
		c = getchar ();
		}
	if (IsNegative)
		b = - b;
	if (ok && Found && !FoundB) {
		fprintf (stderr, "***xyzproject: r g b not found");
		ok = 0;
		}
	Corners = NULL;
	CornerPtr = & Corners;
	while (c == ' ')
		c = getchar ();
	while (c == '+' || c == '-' || (c >= '0' && c <= '9') ) {
		CornerPtr [0] = malloc (sizeof (CornerPtr [0] [0] ) );
		Corner = CornerPtr [0];
		if (ok && CornerPtr [0] == NULL) {
			fprintf (stderr, "***drawpolygons: Not");
			fprintf (stderr, " enough memory");
			ok = 0;
			}
		IsNegative = 0;
		if (c == '+')
			c = getchar ();
		else if (c == '-') {
			IsNegative = 1;
			c = getchar ();
			}
		across = 0;
		while (c >= '0' && c <= '9') {
			across = 10*across + (c - '0');
			c = getchar ();
			}
		if (IsNegative)
			across = - across;
		if (c == ',')
			c = getchar ();
		IsNegative = 0;
		if (c == '+')
			c = getchar ();
		else if (c == '-') {
			IsNegative = 1;
			c = getchar ();
			}
		FoundDown = 0;
		down = 0;
		while (c >= '0' && c <= '9') {
			FoundDown = 1;
			down = 10*down + (c - '0');
			c = getchar ();
			}
		if (IsNegative)
			down = - down;
		if (c == ',')
			c = getchar ();
		if (ok && !FoundDown) {
			fprintf (stderr, "***drawpolygons: Didn't find across,down");
			ok = 0;
			}
		while (c == ' ')
			c = getchar ();
		if (Corner != NULL) {
			Corner->across = across;
			Corner->down = down;
			Corner->next = NULL;
			CornerPtr = & Corner->next;
			}
		}
	if (ok && c != EOF && c != '\n' && c != '#') {
		fprintf (stderr, "***drawpolygons: Found improper");
		fprintf (stderr, " '%c'", c);
		ok = 0;
		}
	while (c != EOF && c != '\n')
		c = getchar ();
	if (Polygon != NULL) {
		Polygon->r = r;
		Polygon->g = g;
		Polygon->b = b;
		Polygon->Corners = Corners;
		Polygon->next = NULL;
		}
	PolygonPtr [0] = Polygon;
	if (c != '\n')
		EndOfInputPtr [0] = 1;
	return ok;
	}


int ReadPolygons (struct Polygon * * PolygonsPtr)
	{
	struct Polygon * * PolygonPtr, * Polygon;
	int EndOfInput, LineNum, ok;

	PolygonPtr = PolygonsPtr;
	ok = 1;
	LineNum = 0;
	EndOfInput = 0 ;
	while (!EndOfInput) {
		LineNum++;
		if (!ReadPolygon (& Polygon, & EndOfInput) ) {
			fprintf (stderr, " in line %d.\n", LineNum);
			ok = 0;
			}
		if (Polygon != NULL) {
			PolygonPtr [0] = Polygon;
			PolygonPtr = & Polygon->next;
			}
		}
	return ok;
	}


void DrawPolygons (struct Polygon * Polygons, int width, int height)
	{
	struct Polygon * Polygon;
	struct Corner * Corner;
	long int a1, d1, a2, d2, a, d;
	int i, j, NumCrossings;

	printf ("P6\n");
	printf ("%d %d\n", width, height);
	printf ("255\n");
	for (i = 0; i < height; i++) {
		d = i - height/2;
		for (j = 0; j < width; j++) {
			a = j - width/2;
			NumCrossings = 0;
			Polygon = Polygons;
			while (Polygon != NULL && NumCrossings == 0) {
				Corner = Polygon->Corners;
				while (Corner != NULL) {
					a1 = Corner->across;
					d1 = Corner->down;
					if (Corner->next == NULL) {
						a2 = Polygon->Corners->across;
						d2 = Polygon->Corners->down;
						}
					else {
						a2 = Corner->next->across;
						d2 = Corner->next->down;
						}
					if (d1 <= d && d < d2 ) {
						if ((a - a1)*(d2 - d1) >= (a2 - a1)*(d - d1) )
							NumCrossings++;
						}
					else if (d1 > d && d >= d2) {
						if ((a - a2)*(d1 - d2) >= (a1 - a2)*(d - d2) )
							NumCrossings--;
						}
					Corner = Corner->next;
					}
				if (NumCrossings != 0) {
					putchar (Polygon->r);
					putchar (Polygon->g);
					putchar (Polygon->b);
					}
				Polygon = Polygon->next;
				}
			if (NumCrossings == 0) {
				putchar (BackgroundR);
				putchar (BackgroundG);
				putchar (BackgroundB);
				}
			}
		}
	}


void WritePolygons (struct Polygon * Polygons)
	{
	struct Polygon * Polygon;
	struct Corner * Corner;

	Polygon = Polygons;
	while (Polygon != NULL) {
		printf ("%d %d %d", Polygon->r, Polygon->g, Polygon->b);
		Corner = Polygon->Corners;
		while (Corner != NULL) {
			printf (" %ld,%ld", Corner->across, Corner->down);
			Corner = Corner->next;
			}
		printf ("\n");
		Polygon = Polygon->next;
		}
	}


void ClosePolygons (struct Polygon * Polygons)
	{
	struct Polygon * Polygon, * NextPolygon;
	struct Corner * Corner, * NextCorner;

	Polygon = Polygons;
	while (Polygon != NULL) {
		NextPolygon = Polygon->next;
		Corner = Polygon->Corners;
		while (Corner != NULL) {
			NextCorner = Corner->next;
			free (Corner);
			Corner = NextCorner;
			}
		free (Polygon);
		Polygon = NextPolygon;
		}
	}

int main (int argc, char * argv [] )
	{
	struct Polygon * Polygons;
	int width, height, ok, i;
	char c;

	if (argc < 2) {
		for (i = 0; i < NumUsageLines; i++)
			printf ("%s\n", UsageLines [i] );
		}
	else if (argc == 3) {
		ok = 1;
		if (sscanf (argv [1], "%d%c", & width, & c) != 1) {
			fprintf (stderr, "***drawpolygons: expecting");
			fprintf (stderr, " width, found");
			fprintf (stderr, " \"%s\".\n", argv [3] );
			ok = 0;
			}
		if (sscanf (argv [2], "%d%c", & height, & c) != 1) {
			fprintf (stderr, "***drawpolygons: expecting");
			fprintf (stderr, " height, found");
			fprintf (stderr, " \"%s\".\n", argv [3] );
			ok = 0;
			}
		if (ok) {
			Polygons = NULL;
			if (ReadPolygons (& Polygons) )
				DrawPolygons (Polygons, width, height);
			else
				WritePolygons (Polygons);
			ClosePolygons (Polygons);
			}
		}
	else {
		fprintf (stderr, "Usage: drawpolygons");
		fprintf (stderr, " (width) (height)\n");
		}
	return 0;
	}