import sys from random import seed, randrange  # ========================================================================== #		Recursive quadtree data structure # ==========================================================================  def quadtree(points,topleft,botright):     if len(points) > 1: #        print >>sys.stderr,"splitting",len(points),topleft,botright         mid = [(topleft[i]+botright[i])*0.5 for i in range(2)]         svgLine((mid[0],topleft[1]),(mid[0],botright[1]))         svgLine((topleft[0],mid[1]),(botright[0],mid[1]))         quadtree([p for p in points if p[0]<mid[0] and p[1]<mid[1]],                  topleft,mid)         quadtree([p for p in points if p[0]<mid[0] and p[1]>=mid[1]],                  (topleft[0],mid[1]),(mid[0],botright[1]))         quadtree([p for p in points if p[0]>=mid[0] and p[1]<mid[1]],                  (mid[0],topleft[1]),(botright[0],mid[1]))         quadtree([p for p in points if p[0]>=mid[0] and p[1]>=mid[1]],                  mid,botright)           # ========================================================================== #		SVG output utility routines # ==========================================================================  nestingLevel = None  def svgTag(s, deltaIndentation = 0): 	"""Send a single XML tag to the SVG file. 	First argument is the tag with all its attributes appended. 	Second arg is +1, -1, or 0 if tag is open, close, or both respectively. 	"""  	global nestingLevel 	if deltaIndentation < 0: 		nestingLevel -= 1 	if nestingLevel: 		sys.stdout.write('\t' * nestingLevel) 	sys.stdout.write('<') 	if deltaIndentation < 0: 		sys.stdout.write('/') 	sys.stdout.write(s) 	if not deltaIndentation: 		sys.stdout.write(' /') 	sys.stdout.write('>\n') 	if deltaIndentation > 0: 		nestingLevel += 1 	  def svgHeader(maxX, maxY): 	"""Start producing an SVG object. 	The output bounding box runs from (0,0) to (maxX,maxY). 	Must be followed by svg content and a call to svgTrailer(). 	""" 	global nestingLevel 	if nestingLevel is None: 		sys.stdout.write('''<?xml version="1.0" encoding="iso-8859-1"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"  "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> ''') 		nestingLevel = 0 	svgTag('svg xmlns="http://www.w3.org/2000/svg" version="1.1" ' 		   'width="%dpt" height="%dpt" viewBox="0 0 %d %d"' 			% (maxX, maxY, maxX, maxY), 1)  def svgTrailer(): 	"""End of SVG object.""" 	svgTag('svg', -1)  def svgStyle(style): 	"""Start a group of svg items with the given style. 	Argument is a string in the form of a list of svg item attributes. 	Must be followed by svg content and a call to svgEndStyle(). 	""" 	svgTag('g ' + style, 1) 	 def svgEdgeStyle(index): 	"""Look up edge style and call svgStyle with it.""" 	svgStyle(globals()['edgeStyle' + str(index)])  def svgEndStyle(): 	"""Finish group of styled svg items.""" 	svgTag('g', -1)  def svgLine(start, end): 	"""Output line segment from start to end coordinates. 	Must be called within an svgStyle()/svgEndStyle() call pair. 	""" 	svgTag('line x1="%d" y1="%d" x2="%d" y2="%d"' % (start+end) )  def svgCircle(center, radius): 	"""Output circle with given center and radius coordinates. 	Must be called within an svgStyle()/svgEndStyle() call pair. 	""" 	svgTag('circle cx="%d" cy="%d" r="%s"' % (center+(radius,)) )    # ========================================================================== #		Test code driver # ==========================================================================  seed(27)  svgRadius = 2 svgBound = 400 margin = 4  def clusteredCoordinate(clusteringExponent,fractalExponent):     x = long(randrange(1000)**clusteringExponent)     y = 0     p = 1     while x:         if x & 1:             y += p         p *= fractalExponent         x >>= 1     return y  def clusteredPoint():     return clusteredCoordinate(2,2.5),clusteredCoordinate(1.5,3.2)  points = [clusteredPoint() for i in range(250)] maxX = max(x for x,y in points) maxY = max(y for x,y in points) scaleX = 1.0*(svgBound-2*margin)/maxX scaleY = 1.0*(svgBound-2*margin)/maxY points = [(x*scaleX+margin,y*scaleY+margin) for x,y in points]  svgHeader(svgBound,svgBound)  svgStyle('fill="none" stroke="blue"') svgLine((1,1),(1,svgBound-1)) svgLine((1,svgBound-1),(svgBound-1,svgBound-1)) svgLine((svgBound-1,svgBound-1),(svgBound-1,1)) svgLine((svgBound-1,1),(1,1)) quadtree(points,(1,1),(svgBound-1,svgBound-1)) svgEndStyle()  svgStyle('fill="white" stroke="black"') for p in points:     svgCircle(p,svgRadius) svgEndStyle()  svgTrailer()