#
# Eksamen 1998 Juni 4
#
# Tue May 18 15:24:24 1999 -- Jens Svalgaard Frederiksen
#

# a)

# PunktType kan implemeteres som tupler af længde 1 sammen med

def makePunktType(x,y,z):
  return (float(x),float(y),float(z))


from math import sqrt

def afstand((p1,p2,p3),(q1,q2,q3)):
  return sqrt( (p1-q1)**2 + (p2-q2)**2 + (p3-q3)**2)


# b)

# NB: floor runder nedad - præcis som vi har brug for
from math import floor

# key giver mapping-nøglen, der bruges i en PunktmgdType
def key(p):
  return (floor(p[0]),floor(p[1]),floor(p[2]))


def insert(pmgd, p):
  k = key(p)
  
  if pmgd.has_key(k):
    pmgd[k].append(p)
  else:
    pmgd[k] = [p]

# c)

def omegn(pmgd,p):
  result = []
  
  k = key(p)
  
  # Prøv alle de 27 "omegne" af p's nøgle af
  for dx in [-1,0,1]:
    for dy in [-1,0,1]:
      for dz in [-1,0,1]:
	khere = (k[0]+dx, k[1]+dy, k[2]+dz)
	
	if pmgd.has_key(khere):
	  for q in pmgd[khere]:
	    if afstand(p,q) < 1:
	      result.append(q)
	      
  return result