Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: TrinityNoe on Sep 3rd, 2011  |  syntax: Python  |  size: 0.68 KB  |  views: 311  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. def dist(a,b):
  2.     return max(abs(a[0] - b[0]),abs(a[1] - b[1]))
  3. def cab_dist(a,b):
  4.     return abs(a[0] - b[0]) + abs(a[1] - b[1])
  5. def go():
  6.     N = int(raw_input())
  7.     lis = []
  8.     for q in xrange(N):
  9.         point = [int(x) for x in  raw_input().split()]
  10.         lis.append(point)
  11.     sumx = int(sum([x[0] for x in lis ])/q)
  12.     sumy = int(sum([x[1] for x in lis ])/q)
  13.     p = (sumx,sumy)
  14.     x = [ (sumx + n, sumy + m) for n in xrange(0,2) for m in xrange(0,2)]
  15.     dis1 = [ (cab_dist(y,p),y) for y in lis for p in x]
  16.     mi = min(dis1)[0]
  17.     dis1 = [ x[1] for x in dis1 if x[0]==mi]
  18.     dis2 = [ (sum([dist(y,p) for y in lis]),p) for p in dis1 ]
  19.     print min(dis2)[0]
  20. go()
clone this paste RAW Paste Data