//#define _GNU_SOURCE

#include <ctype.h>
#include <search.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>


struct point {
	int x;
	int y;
};


struct point *
point_create(int x, int y)
{
	struct point * p = malloc(sizeof(struct point));
	if (!p)
		return NULL;
	p->x = x;
	p->y = y;
	return p;
}


struct point *
point_copy(struct point const * other)
{
	return point_create(other->x, other->y);
}


int
point_cmp(struct point const * a, struct point const * b)
{
	return a->x - b->x != 0
		? a->x - b->x
		: a->y - b->y;
}


int
point_tcmp(void const * a, void const * b)
{
	return point_cmp(a, b);
}


int
main(int argc, char ** argv)
{
	int len = 2, i;
	char buf[BUFSIZ];
	struct point * rope;
	void * tails = NULL;
	int ntails = 0;

	while ((i = getopt(argc, argv, "p:l:")) != -1) {
		switch (i) {
		case 'p':
			switch (atoi(optarg)) {
			case 1: len = 2; break;
			case 2: len = 10; break;
			default:
				fprintf(stderr, "Unexpected part: %s\n", optarg);
				return -1;
			}
			break;

		case 'l':
			len = atoi(optarg);
			if (len < 2) {
				fprintf(stderr, "Unexpected length: %d\n", len);
				return -1;
			}
			break;

		default:
			return -1;
		}
	}

	rope = malloc(len * sizeof(struct point));
	for (i = 0; i < len; ++i) {
		rope[i].x = rope[i].y = 0;
	}

	tsearch(point_create(0, 0), &tails, point_tcmp);
	++ntails;

	while (fgets(buf, sizeof(buf), stdin)) {
		int dist;

		if (!isalpha(buf[0])
				|| buf[1] != ' '
				|| !isdigit(buf[2]))
		{
			fprintf(stderr, "Unexpected input: %s\n", buf);
			return -1;
		}

		dist = atoi(buf + 2);
		if (dist == 0) {
			fprintf(stderr, "Unexpected distance in: %s\n", buf);
			// Allow 0 for now...
		}
		while (dist > 0) {
			int seg;

			switch (buf[0]) {
				case 'L': --rope[0].x; break;
				case 'R': ++rope[0].x; break;
				case 'U': ++rope[0].y; break;
				case 'D': --rope[0].y; break;
				default:
					  fprintf(stderr, "Unexpected input: %s\n", buf);
					  return -1;
			}

			for (seg = 1; seg < len; ++seg) {
				int dx, dy;

				dx = rope[seg - 1].x - rope[seg].x;
				dy = rope[seg - 1].y - rope[seg].y;

				if (dx * dx + dy * dy <= 2)
					break;

				if (dx > 0)
					++rope[seg].x;
				if (dx < 0)
					--rope[seg].x;
				if (dy > 0)
					++rope[seg].y;
				if (dy < 0)
					--rope[seg].y;
			}

			if (seg == len) {
				// Had to move all segments, including tail.
				// Check if it's a new tail pos
				struct point * tail, ** pp;

				// Search/insert current tail in visited tails
				tail = point_copy(rope + len - 1);
				pp = tsearch(tail, &tails, point_tcmp);
				if (*pp == tail) {
					// This was a new one, tail is now in the tree
					++ntails;
				}
				else {
					// Tail already in tree, free the one we just created.
					free(tail);
				}
			}

			--dist;
		}
	}

	printf("Unique tail spots visited: %d\n", ntails);

	free(rope);
#ifdef _GNU_SOURCE
	tdestroy(tails, free);
#endif

	return 0;
}