usr bin env python coding utf-8 import sys eps 1e-5 def read_input sti

#!/usr/bin/env python
# -*- coding: utf-8 -*- 

import sys

eps = 1e-5


def read_input():
    sticks = []

    for line in input.readlines():
        x1,y1,x2,y2 = map(float, line.strip().split(';'))
        sticks.append( ((x1,y1),(x2,y2)) )

    return sticks

def intersect(s1, s2):
    if max([s1[0][0],s1[1][0]]) < min([s2[0][0],s2[1][0]]) or \
        max([s1[0][1],s1[1][1]]) < min([s2[0][1],s2[1][1]]) or \
         max([s2[0][0],s2[1][0]]) < min([s1[0][0],s1[1][0]]) or \
          max([s2[0][1],s2[1][1]]) < min([s1[0][1],s1[1][1]]):
              return False
    z  = (s1[1][1]-s1[0][1])*(s2[0][0]-s2[1][0])-(s2[0][1]-s2[1][1])*(s1[1][0]-s1[0][0])
    ca = (s1[1][1]-s1[0][1])*(s2[0][0]-s1[0][0])-(s2[0][1]-s1[0][1])*(s1[1][0]-s1[0][0])
    cb = (s2[0][1]-s1[0][1])*(s2[0][0]-s2[1][0])-(s2[0][1]-s2[1][1])*(s2[0][0]-s1[0][0])

    if sum(map(abs,[z,ca,cb]))<eps:
        # on one line. compare xs
        if (s1[0][0] <= s2[0][0] <= s1[1][0] or 
                s1[0][0] <= s2[1][0] <= s1[1][0]) and s1[0][0]!=s1[1][0]:
            return True
        if (s1[0][1] <= s2[0][1] <= s1[1][1] or 
            s1[0][1] <= s2[1][1] <= s1[1][1]) and s1[0][1]!=s1[1][1]:
                return True
        return False
    if z == 0:
        return False 

    ua=ca/z
    ub=cb/z

    if 0 <= ua <= 1 and 0 <= ub <= 1:
        return True
    return False




def count_piles(sticks):
    n = len(sticks)
    piles = []

    for i in xrange(n):
        for j in xrange(i+1,n):
            if intersect(sticks[i], sticks[j]):
                piles.append(set((i+1,j+1)))
        piles.append(set([i+1]))

    def reduce_piles(acc, pile):
        for p1 in acc:
            if pile & p1 != set():
                p1 |= pile
                return acc
        acc.append(pile)
        return acc

    reduced_piles = reduce(reduce_piles, piles, [])
    r2 = reduce(reduce_piles, piles, [])
    while r2 != reduced_piles:
        reduced_piles = r2
        r2 = reduce(reduce_piles, piles, [])

    for pile in reduced_piles:
        print ';'.join(map(str,sorted(pile)))

def generate_random_sticks(width, height, num):
    from random import randint
    from StringIO import StringIO
    res = []
    for i in range(num):
        res.append(';'.join(map(str,[randint(0,width), randint(0,height), randint(0,width), randint(0,height)])))
    return StringIO('\n'.join(res))

def draw_sticks(sticks, file):
    import Image, ImageDraw
    magn = 50
    max_x = max(x for pair in map(lambda s: (s[0][0], s[1][0]), sticks) for x in pair)
    max_y = max(x for pair in map(lambda s: (s[0][1], s[1][1]), sticks) for x in pair)
    im = Image.new("RGB",map(int,(max_x*magn, max_y*magn)), (255,255,255))
    draw = ImageDraw.Draw(im)
    for s in sticks:
        draw.line(map(lambda x: x*magn, s[0]+s[1]),fill=(0,0,0))
    im.save("/tmp/sticks.png")
    im.show()


if __name__ == '__main__':
#    input = sys.stdin
#    input = open('input12.dat')
    input = generate_random_sticks(width=10,height=10,num=5)
    sticks = read_input()
    print sticks
    draw_sticks(sticks, '/tmp/sticks.png')
    count_piles(sticks)