#include <cassert>
#include <cmath>
#include <stdint.h>

typedef int64_t Scalar;

struct Fraction
{
	Scalar n;
	Scalar d; // must be >= 0

	Fraction() {}
	Fraction(Scalar numerator, Scalar denominator) : n(numerator), d(denominator)
	{
		if(d < 0)
		{
			n = -n;
			d = -d;
		}
	}

	Scalar operator*(Scalar arg) const { assert(d != 0); return arg * n / d; }

	bool IsNormal() const { return 0 <= n && n <= d; }
};

struct Coords
{
	Scalar x;
	Scalar y;

	Coords() {}
	Coords(Scalar xx, Scalar yy) : x(xx), y(yy) {}

	bool operator==(const Coords &arg) const { return (x == arg.x) && (y == arg.y); }

	Coords operator+(const Coords &arg) const { return Coords(x + arg.x, y + arg.y); }
	Coords operator-(const Coords &arg) const { return Coords(x - arg.x, y - arg.y); }

	bool IsZero() const { return (x | y) == 0; }
};

struct Vector
{
	Coords c;

	Vector() {}
	Vector(const Coords &cc) : c(cc) {}

	bool operator==(const Vector &arg) const { return c == arg.c; }

	Vector operator+(const Vector &arg) const { return Vector(c + arg.c); }
	Vector operator-(const Vector &arg) const { return Vector(c - arg.c); }

	Scalar operator*(const Vector &arg) const { return c.x * arg.c.x + c.y * arg.c.y; }
	Scalar operator^(const Vector &arg) const { return c.x * arg.c.y - c.y * arg.c.x; }

	Vector operator*(const Fraction &arg) const { return Vector(Coords(arg*c.x, arg*c.y)); }

	double Angle() const { return c.IsZero() ? 0 : std::atan2(-c.y, c.x); }
};

struct Point
{
	Coords c;

	Point() {}
	Point(const Coords &cc) : c(cc) {}

	bool operator==(const Point &arg) const { return c == arg.c; }

	Point operator+(const Vector &arg) const { return Point(c + arg.c); }
	Point operator-(const Vector &arg) const { return Point(c - arg.c); }

	Vector operator-(const Point &arg) const { return Vector(c - arg.c); }

	bool operator<(const Point &arg) const { return c.y < arg.c.y || (c.y == arg.c.y && c.x < arg.c.x); }
};

struct Segment
{
	// { p + t * v, where 0 < t < 1 }
	Point p1;
	Point p2;

	Segment() {}
	Segment(const Point &pp1, const Point &pp2) : p1(pp1), p2(pp2) {}

	bool operator==(const Segment &arg) const { return p1 == arg.p1 && p2 == arg.p2; }
	Segment operator-() const { return Segment(p2, p1); }
};

enum IntersectResult
{
	IntersectNo, // no intersection at all
	IntersectOk, // exactly one intersection
	IntersectOverlap // special case: overlapping segments
};

inline IntersectResult Intersect(const Segment &arg1, const Segment &arg2, Point &p)
{
	Vector v1(arg1.p2 - arg1.p1);
	Vector v2(arg2.p2 - arg2.p1);
	Vector v3(arg2.p1 - arg1.p1);
	Scalar d = v1 ^ v2;
	if(d)
	{
		Fraction f1(v3 ^ v2, d);
		Fraction f2(v3 ^ v1, d);
		if(f1.IsNormal() && f2.IsNormal())
		{
			p = Point(arg1.p1 + v1 * f1);
			return IntersectOk;
		}
	}
	else
	{
		assert(!v1.c.IsZero());

		// Now we know that arg1 and arg2 are collinear

		if((v3 ^ v1) == 0)
		{
			// Now we know that arg1 and arg2 lie exactly on the same line

			Scalar proj11 = 0; // v1 * (arg1.p1 - arg1.p1) == v1 * 0 == 0
			Scalar proj12 = v1 * v1; // v1 * (arg1.p2 - arg1.p1) > 0
			Scalar proj21 = v1 * (arg2.p1 - arg1.p1);
			Scalar proj22 = v1 * (arg2.p2 - arg1.p1);
			if(proj21 > proj22) { Scalar tmp = proj21; proj21 = proj22; proj22 = tmp; }

			if(proj11 < proj22 && proj21 < proj12)
			{
				// Now we know that arg1 and arg2 have noteworthy intersection

				return IntersectOverlap;
			}
		}
	}
	return IntersectNo;
}

#include "algebra.h"

#include <vector>
#include <list>
#include <set>
#include <map>
#include <iterator>

#include <cassert>
#include <stdint.h>

class Graph
{
	typedef std::map< Point, std::map<double, Vector> > Container;
	typedef Container::iterator iterator;
	typedef Container::const_iterator const_iterator;

	Container graph;

public:

	size_t Size() const
	{
		size_t ret = 0;
		for(const_iterator fi = graph.begin(), la = graph.end(); fi != la; ++fi)
		{
			ret += fi->second.size();
		}
		return ret;
	}

	void InsertBranch(const Segment &s)
	{
		Point p(s.p1);
		Vector v(s.p2-s.p1);

		graph[p][v.Angle()] = v;
	}

	void EraseBranch(const Segment &s)
	{
		Point p(s.p1);
		Vector v(s.p2-s.p1);

		iterator it = graph.find(p);
		if(it != graph.end())
		{
			it->second.erase(v.Angle());
			if(it->second.empty())
			{
				graph.erase(it);
			}
		}
	}

	void Envelope(std::vector<Segment> &dst) const
	{
		dst.clear();

		if(graph.empty()) return;

		size_t size = Size();

		Point p0(graph.begin()->first);
		Vector v0(graph.begin()->second.begin()->second);

		Point p1(p0);
		Vector v1(v0);

		do
		{
			Point p2(p1 + v1);
			Vector v2(p1 - p2);

			assert(dst.size() < size);
			dst.push_back(Segment(p1, p2));

			const_iterator g_i = graph.find(p2);
			assert(g_i != graph.end());

			std::map<double, Vector>::const_iterator b_i = g_i->second.upper_bound(v2.Angle());
			if(b_i == g_i->second.end()) b_i = g_i->second.begin();

			p1 = p2;
			v1 = b_i->second;
		}
		while(! (p1 == p0));
	}
};

class Builder
{
	typedef std::list<Segment> Container;
	typedef Container::iterator iterator;
	typedef Container::const_iterator const_iterator;

	Container segments;
	Point first_point;
	Point last_point;

	Graph graph;

	void EraseSegment(const iterator &it)
	{
		Segment s(*it);
		segments.erase(it);

		graph.EraseBranch(s);
		graph.EraseBranch(-s);
	}

	void InsertSegment(const Point &p1, const Point &p2)
	{
		Segment s(p1, p2);
		segments.push_front(s);

		graph.InsertBranch(s);
		graph.InsertBranch(-s);
	}

	void SplitSegment(const iterator &it, const Point &p)
	{
		if(it->p1 == p || it->p2 == p) return; // ignore zero-size segments

		InsertSegment(it->p1, p);
		InsertSegment(it->p2, p);
		EraseSegment(it);
	}

	iterator AppendPoint(Point next_point)
	{
		if(next_point == last_point) return segments.begin(); // ignore zero-size segments

		Segment new_segment(last_point, next_point);

		std::set<Point> new_points;
		new_points.insert(last_point);
		new_points.insert(next_point);

		assert(new_points.size() == 2);

		last_point = next_point;

		for(iterator i = segments.begin(); i != segments.end(); )
		{
			iterator next_i = i;
			++next_i;
			Point common_point;
			switch(Intersect(new_segment, *i, common_point))
			{
				case IntersectOk:
					new_points.insert(common_point);
					SplitSegment(i, common_point);
					break;
				case IntersectOverlap:
					new_points.insert(i->p1);
					new_points.insert(i->p2);
					EraseSegment(i);
					break;
				case IntersectNo:
					break;
			}
			i = next_i;
		}

		iterator ret = segments.begin();

		for(std::set<Point>::iterator i = new_points.begin(), j = i++; i != new_points.end(); j = i++)
		{
			InsertSegment(*i, *j);
		}

		return ret;
	}

public:
	Builder(Scalar x, Scalar y) : first_point(Coords(x, y)), last_point(first_point) {}
	void Push(Scalar x, Scalar y)
	{
		AppendPoint(Point(Coords(x, y)));
	}
	void Draw(std::vector<Segment> &dst1, std::vector<Segment> &dst2, std::vector<Segment> &dst3)
	{
		dst1.clear();
		dst2.clear();
		dst3.clear();

		if(segments.empty()) return;

		Builder scratch(*this);
		iterator it = scratch.AppendPoint(first_point);
		dst2.assign(scratch.segments.begin(), it);
		dst1.assign(it, scratch.segments.end());
		scratch.graph.Envelope(dst3);
	}
};

#include "builder.h"

#include <SDL/SDL.h>
#include <stdio.h>
#include <stdlib.h> // for exit()

#define SCREEN_X 640
#define SCREEN_Y 480

void DrawNode(SDL_Surface *surface, const Point &p, Uint32 color)
{
	SDL_Rect rt;
	rt.x = p.c.x - 2;
	rt.y = p.c.y - 2;
	rt.w = 5;
	rt.h = 5;
	SDL_FillRect(surface, &rt, color);
}

void DrawPixel(SDL_Surface *surface, const Point &pp, Uint32 color)
{
	int bpp = surface->format->BytesPerPixel;
	Uint8 *p = (Uint8 *)surface->pixels + pp.c.y * surface->pitch + pp.c.x * bpp;

	switch (bpp)
	{
		case 1:
			*p = color;
			break;
		case 2:
			*(Uint16 *)p = color;
			break;
		case 3:
			if (SDL_BYTEORDER == SDL_BIG_ENDIAN) {
					p[0] = (color >> 16) & 0xff;
					p[1] = (color >> 8) & 0xff;
					p[2] = color & 0xff;
			}
			else
			{
					p[0] = color & 0xff;
					p[1] = (color >> 8) & 0xff;
					p[2] = (color >> 16) & 0xff;
			}
			break;
		case 4:
			*(Uint32 *)p = color;
			break;
		default:
			break;
	}
}

void DrawLine(SDL_Surface *surface, Point p1, const Point &p2, Uint32 color)
{
	Scalar dx = abs(p2.c.x - p1.c.x);
	Scalar dy = abs(p2.c.y - p1.c.y);
	Scalar sx = (p2.c.x > p1.c.x) ? 1 : -1;
	Scalar sy = (p2.c.y > p1.c.y) ? 1 : -1;
	Scalar er = dx - dy;

	while(! (p1 == p2))
	{
		DrawPixel(surface, p1, color);
		Scalar e2 = 2*er;
		if(e2 > -dy)
		{
			er -= dy;
			p1.c.x += sx;
		}
		if(e2 < dx)
		{
			er += dx;
			p1.c.y += sy;
		}
	}

	DrawPixel(surface, p1, color);
}

void DrawSegments(SDL_Surface *surface, const std::vector<Segment> &segments, Uint32 color)
{
	for(size_t i = 0, size = segments.size(); i < size; ++i)
	{
		Point p1(segments[i].p1);
		Point p2(segments[i].p2);
		DrawNode(surface, p1, color);
		DrawNode(surface, p2, color);
		DrawLine(surface, p1, p2, color);
	};
}

void UpdateScreen(const std::vector<Segment> &s1, const std::vector<Segment> &s2, const std::vector<Segment> &s3)
{
	SDL_Surface *surface = SDL_GetVideoSurface();
	if(surface == 0)
	{
		fprintf(stderr, "Couldn't get surface: %s.\n", SDL_GetError());
		return;
	}

	if(SDL_LockSurface(surface) == -1)
	{
		fprintf(stderr, "Couldn't lock surface: %s.\n", SDL_GetError());
		return;
	}

	SDL_FillRect(surface, 0, SDL_MapRGB(surface->format, 0x00, 0x00, 0x00));
	DrawSegments(surface, s1, SDL_MapRGB(surface->format, 0x7f, 0x7f, 0x7f));
	DrawSegments(surface, s2, SDL_MapRGB(surface->format, 0x00, 0x7f, 0x7f));
	DrawSegments(surface, s3, SDL_MapRGB(surface->format, 0xff, 0xff, 0xff));

	SDL_UnlockSurface(surface);
	SDL_Flip(surface);
}

int main()
{
	if(SDL_Init(SDL_INIT_VIDEO) == -1)
	{
		fprintf(stderr, "Couldn't initialize SDL: %s.\n", SDL_GetError());
		return -1;
	}

	// Clean SDL up on exit
	atexit(SDL_Quit);

	if(SDL_SetVideoMode(SCREEN_X, SCREEN_Y, 8, SDL_HWSURFACE|SDL_DOUBLEBUF|SDL_ANYFORMAT) == 0)
	{
		fprintf(stderr, "Couldn't set %dx%d video mode: %s\n", SCREEN_X, SCREEN_Y, SDL_GetError());
		return -1;
	}

	Builder builder(SCREEN_X/2, SCREEN_Y/2);
	std::vector<Segment> scratch1, scratch2, scratch3;

	SDL_Event event;
	while( SDL_WaitEvent(&event) >= 0 )
	{
		switch (event.type)
		{
			case SDL_MOUSEBUTTONDOWN:
				{
					builder.Push(event.button.x, event.button.y);
					builder.Draw(scratch1, scratch2, scratch3);
					UpdateScreen(scratch1, scratch2, scratch3);
				}
				break;
			case SDL_QUIT:
				fprintf(stderr, "Quit requested\n");
				return 0;
			default:
				break;
		}
	}

	return 0;
}

--- old/builder.h       2011-02-09 00:35:32.541534076 +0300
+++ new/builder.h       2011-02-09 00:24:23.175373666 +0300
@@ -34,7 +34,8 @@
       Point p(s.p1);
       Vector v(s.p2-s.p1);
 
-      graph[p][v.Angle()] = v;
+      bool ok = graph[p].insert(std::make_pair(v.Angle(), v)).second;
+      assert(ok);
    }
 
    void EraseBranch(const Segment &s)
@@ -77,9 +78,10 @@
 
          const_iterator g_i = graph.find(p2);
          assert(g_i != graph.end());
+         std::map<double, Vector>::const_iterator b_i = g_i->second.find(v2.Angle());
+         assert(b_i != g_i->second.end());
 
-         std::map<double, Vector>::const_iterator b_i = g_i->second.upper_bound(v2.Angle());
-         if(b_i == g_i->second.end()) b_i = g_i->second.begin();
+         if(++b_i == g_i->second.end()) b_i = g_i->second.begin();
 
          p1 = p2;
          v1 = b_i->second;
@@ -120,11 +122,15 @@
 
    void SplitSegment(const iterator &it, const Point &p)
    {
-      if(it->p1 == p || it->p2 == p) return; // ignore zero-size segments
+      Point p1(it->p1);
+      Point p2(it->p2);
+
+      if(p1 == p || p2 == p) return; // ignore zero-size segments
 
-      InsertSegment(it->p1, p);
-      InsertSegment(it->p2, p);
       EraseSegment(it);
+
+      InsertSegment(p1, p);
+      InsertSegment(p2, p);
    }
 
    iterator AppendPoint(Point next_point)