Advertisement
Guest User

Untitled

a guest
Apr 19th, 2018
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.96 KB | None | 0 0
  1. def s_t(i, j, q):
  2. return abs(((l[j][0] - l[i][0]) * (l[j][1] + l[i][1]) + (l[q][0] - l[j][0]) * (l[q][1] + l[j][1]) + (
  3. l[i][0] - l[q][0]) * (l[i][1] + l[q][1])) / 2)
  4.  
  5.  
  6. n = int(input())
  7. l = [list(map(int, input().split())) for i in range(n)] * 2
  8. s = 0
  9. for i in range(n):
  10. s += (l[i + 1][0] - l[i][0]) * (l[i + 1][1] + l[i][1]) / 2
  11. s = abs(s)
  12. eps = 1e-18
  13. ans2 = 10 ** 19
  14. j = 0
  15. q = 1
  16. s1 = 0
  17. a, b = -1, -1
  18. cur_s = -1e18
  19. while j < n and q < n:
  20. ans1 = -1e18
  21. while q < n and (min(s - s1, s1) / max(s - s1, s1) > ans1:
  22. q += 1
  23. ans1 = min(s - s1, s1) / max(s - s1, s1)
  24. s1 += s_t(q, j, q - 1)
  25. q -= 1
  26. s1 -= s_t(q, q + 1, j)
  27. if cur_s < min(s - s1, s1) / max(s - s1, s1)):
  28. cur_s = min(s - s1, s1) / max(s - s1, s1))
  29. a = j
  30. b = q
  31. j += 1
  32. if j == q:
  33. q += 1
  34. s1 = 0
  35. else:
  36. s1 -= s_t(j, j - 1, q)
  37.  
  38.  
  39. print(a + 1, b + 1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement