прикреплённый файл:growing_circles.py к странице LecturesVMSH/2011-03-02

   1 # coding: UTF8
   2 # by Pavel Sutyrin
   3 #
   4 # Растущие окружности. 
   5 #
   6 # На плоскости даны координаты N точек (пар
   7 # вещественных чисел). Из этих точек как из центров начинают расти
   8 # окружности с одинаковой скоростью. Когда любые две окружности начинаются
   9 # касаться, то их рост прекращается и радиусы фиксируются. Через некоторое
  10 # конечное время рост всех окружностей прекращается. Напечатать N
  11 # окончательных радиусов окружностей. Кроме всего прочего, нарисовать
  12 # условие (и результат) задачи в графическом виде. 
  13 
  14 import math
  15 from random import randrange
  16 
  17 circles = []
  18 #n = input()
  19 #for i in range(n):
  20   #circles.append( [(input(), input()), -1.0] ) # center, radius; -1 means unassigned
  21 
  22 n = 50
  23 for i in range(n):
  24   circles.append( [(randrange(800)+200, randrange(600)+100), -1.0] ) # center, radius; -1 means unassigned
  25 
  26 def dist(p1, p2):
  27   return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
  28 
  29 pairs = [(i,j) for i in range(n) for j in range(n) if i < j]
  30 
  31 pairs.sort(lambda p1, p2: cmp( dist(circles[p1[0]][0], circles[p1[1]][0]),\
  32                                dist(circles[p2[0]][0], circles[p2[1]][0])))
  33 
  34 for i, j in pairs:
  35   d = dist(circles[i][0], circles[j][0])
  36 
  37   if circles[i][1] < 0 and circles[j][1] < 0:
  38     circles[i][1] = circles[j][1] = d/2.0
  39   elif circles[i][1] < 0:
  40     circles[i][1] = d - circles[j][1]
  41   elif circles[j][1] < 0:
  42     circles[j][1] = d - circles[i][1]
  43   else:
  44     if circles[i][1] + circles[j][1] >= d:
  45       print "SHOULD NOT HAPPEN: ", i, j
  46 
  47 for c in circles:
  48   print c