Advertisement
Guest User

Untitled

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