SHARE
TWEET

Untitled

TrinityNoe Sep 3rd, 2011 314 Never
  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()
RAW Paste Data
Top