import sys
from random import seed, randrange

# ==========================================================================
# 		Recursive quadtree data structure
# ==========================================================================


def quadtree(points, topleft, botright):
    if len(points) > 1:
        print("splitting", len(points), topleft, botright, file=sys.stderr)  
        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 = int(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()