Advertisement
Doktorkrab

YA LALKA

Mar 28th, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.98 KB | None | 0 0
  1. class Vector:
  2.     def __init__(self, x, y):
  3.         self.x = x
  4.         self.y = y
  5.  
  6.     def __neg__(self):
  7.         return Vector(-self.x, -self.y)
  8.  
  9.     def __add__(self, other):
  10.         return Vector(self.x + other.x, self.y + other.y)
  11.  
  12.     def __sub__(self, other):
  13.         return Vector(self.x - other.x, self.y - other.y)
  14.  
  15.     def __mul__(self, k):
  16.         return Vector(k * self.x, k * self.y)
  17.  
  18.     def __rmul__(self, k):
  19.         return Vector(k * self.x, k * self.y)
  20.  
  21.  
  22. def lenv(a, b):
  23.     return ((a.x - b.x) ** 2 + (a.y - b.y) ** 2) ** 0.5
  24. n, l, k = map(int,input().split())
  25. if k > 0:
  26.     holes = set(map(lambda x: int(x) - 1, input().split()))
  27. else:
  28.     holes = {}
  29. fence = []
  30. for i in range(n):
  31.     x, y = map(int, input().split())
  32.     fence.append(Vector(x, y))
  33. ansM = 0
  34. s = 0
  35. for num in holes:
  36.     nowl = l
  37.     ansNow = 0
  38.     pos = num
  39.     flag = False
  40.     s += lenv(fence[num], fence[(num + 1) % n])
  41.     while nowl > 0 and not (flag and pos == num):
  42.         if pos in holes:
  43.             tmp = lenv(fence[pos], fence[(pos + 1) % n])
  44.             if tmp <= nowl:
  45.                 ansNow += tmp
  46.                 nowl -= tmp
  47.             else:
  48.                 ansNow += nowl
  49.                 nowl = 0
  50.         else:
  51.             nowl -= lenv(fence[pos], fence[(pos + 1) % n])
  52.         pos += 1
  53.         pos %= n
  54.         flag = True
  55.     #print(num, ansNow)
  56.     ansM = max(ansM, ansNow)
  57.     nowl = l
  58.     ansNow = 0
  59.     pos = num
  60.     flag = False
  61.     while nowl > 0 and not (flag and pos == num):
  62.         if pos in holes:
  63.             tmp = lenv(fence[pos], fence[(pos - 1) % n])
  64.             if tmp <= nowl:
  65.                 ansNow += tmp
  66.                 nowl -= tmp
  67.             else:
  68.                 ansNow += nowl
  69.                 nowl = 0
  70.         else:
  71.             nowl -= lenv(fence[pos], fence[(pos - 1) % n])
  72.         pos -= 1
  73.         pos %= n
  74.         flag = True
  75.     #print(num, ansNow)
  76.     ansM = max(ansM, ansNow)
  77. print('{:.6f}'.format(s - ansM))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement