Advertisement
Doktorkrab

Untitled

Mar 28th, 2017
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.30 KB | None | 0 0
  1. class Vector:
  2.     def __init__(self, x, y):
  3.         self.x = x
  4.         self.y = y
  5.  
  6.  
  7. def lenv(a, b):
  8.     return ((a.x - b.x) ** 2 + (a.y - b.y) ** 2) ** 0.5
  9. n, l, k = map(int, input().split())
  10. if k:
  11.     holes = list(map(lambda x: int(x) - 1, input().split()))
  12. else:
  13.     holes = []
  14. fence = []
  15. for i in range(n):
  16.     x, y = map(int, input().split())
  17.     fence.append(Vector(x, y))
  18. fromz = 0
  19. pos = 0
  20. l1 = 0
  21. hl = [0]
  22. ans = 0
  23. for i in range(n):
  24.     if i == holes[pos] and not pos:
  25.         fromz = l1
  26.         l1 = 0
  27.         pos += 1
  28.         pos %= k
  29.     elif i == holes[pos]:
  30.         hl.append(l1)
  31.         l1 = 0
  32.         pos += 1
  33.         pos %= k
  34.     else:
  35.         l1 += lenv(fence[i], fence[(i + 1) % n])
  36.     i += 1
  37.     i %= n
  38. hl[0] = l1 + fromz
  39. s = 0
  40. for hole_ind in range(k):
  41.     s += lenv(fence[holes[hole_ind]], fence[(holes[hole_ind] + 1) % n])
  42.     nowl = l
  43.     ansn = 0
  44.     ind = hole_ind
  45.     flag = False
  46.     while nowl > 0 and not (flag and ind == hole_ind):
  47.         pos = holes[ind]
  48.         tmp = lenv(fence[pos], fence[(pos + 1) % n])
  49.         if tmp <= nowl:
  50.             ansn += tmp
  51.             nowl -= tmp
  52.         else:
  53.             ansn += nowl
  54.             nowl = 0
  55.         nowl -= hl[ind]
  56.         ind = (ind + 1) % k
  57.     ans = max(ansn, ans)
  58. print(s - ans)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement