Помогите решить олимпиадную задачу по информатике "Силовое поле"
Нужна помощь по задаче из олимпиадной информатики. Я застопорился на одном из номеров, условие которого вы видете выше. Я написал код, но на 3 тесте он выдает неверный ответ. Честно пытался разобраться почему, но так и не получилось
Вот код:
import math
def sort_coordinates(cs):
cx = sum(c[0] for c in cs) / len(cs)
cy = sum(c[1] for c in cs) / len(cs)
sorted_cs = sorted(cs, key=lambda v: math.atan2(v[1] - cy, v[0] - cx) if math.atan2(v[1] - cy, v[0] - cx) >= 0 else math.atan2(v[1] - cy, v[0] - cx) + 2 * math.pi)
return sorted_cs
def fig_area(x, y):
s = 0
for i in range(0, len(x)):
if i + 1 > len(x) - 1:
i1 = 0
else:
i1 = i + 1
s += x[i]*(y[i1]-y[i-1])
return 1/2*abs(s)
N, Q = map(int, input().split())
coordinates = []
res = []
for _ in range(N):
x, y = map(int, input().split())
coordinates.append([x, y])
for _ in range(Q):
i, x, y = map(int, input().split())
coordinates[i - 1] = [x, y]
sorted_coordinates = sort_coordinates(coordinates)
xs = [p[0] for p in sorted_coordinates]
ys = [p[1] for p in sorted_coordinates]
res.append(fig_area(xs, ys))
for answ in res:
print("{:.2f}".format(answ))
Для нахождения площади я использовал формулу Гаусса: https://ru.wikipedia.org/wiki/Формула_площади_Гаусса
Сортировка координат идет по полярному углу
Ответы (1 шт):
Не хватает точности при сортировке точек. Первый пример – выпуклый четырёхугольник вытянутый вдоль диагонали:
$ cat temp.txt 4 1 999999999 999999999 1000000000 1000000000 -999999999 -1000000000 -999999998 -1000000000 1 999999999 999999999 $ python temp.py < temp.txt 999999999.00
Второй пример – тот же четырёхугольник отражённый от прямой x = y. Площадь должна быть такой же. Но:
$ cat temp.txt 4 1 999999999 999999999 1000000000 1000000000 -1000000000 -999999999 -1000000000 -999999998 1 999999999 999999999 $ python temp.py < temp.txt 1000000000.50
Площади зеркальных многоугольников отличаются на полторы единицы, что говорит об ошибке в программе.
Я думаю что ошибка вызвана тем что точки (999999999, 999999999) и (1000000000, 1000000000) дают одинаковые значения функции atan2 и, следовательно, не сортируются правильно.
P.S. Как правильно сказали в комментариях, после исправления этой ошибки вы упрётесь в производительность при подсчёте площадей.

