Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def s_t(i, j, q):
- 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]) + (
- l[i][0] - l[q][0]) * (l[i][1] + l[q][1])) / 2)
- n = int(input())
- l = [list(map(int, input().split())) for i in range(n)] * 2
- s = 0
- for i in range(n):
- s += (l[i + 1][0] - l[i][0]) * (l[i + 1][1] + l[i][1]) / 2
- s = abs(s)
- eps = 1e-18
- ans2 = 10 ** 19
- j = 0
- q = 1
- s1 = 0
- a, b = -1, -1
- cur_s = -1e18
- while j < n and q < n:
- ans1 = -1e18
- while q < n and (min(s - s1, s1) / max(s - s1, s1) > ans1:
- q += 1
- ans1 = min(s - s1, s1) / max(s - s1, s1)
- s1 += s_t(q, j, q - 1)
- q -= 1
- s1 -= s_t(q, q + 1, j)
- if cur_s < min(s - s1, s1) / max(s - s1, s1)):
- cur_s = min(s - s1, s1) / max(s - s1, s1))
- a = j
- b = q
- j += 1
- if j == q:
- q += 1
- s1 = 0
- else:
- s1 -= s_t(j, j - 1, q)
- print(a + 1, b + 1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement