Помогите решить олимпиадную задачу по информатике "Силовое поле"

Условие задачи 1 Условие задачи 2

Нужна помощь по задаче из олимпиадной информатики. Я застопорился на одном из номеров, условие которого вы видете выше. Я написал код, но на 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 шт):

Автор решения: Stanislav Volodarskiy

Не хватает точности при сортировке точек. Первый пример – выпуклый четырёхугольник вытянутый вдоль диагонали:

$ 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. Как правильно сказали в комментариях, после исправления этой ошибки вы упрётесь в производительность при подсчёте площадей.

→ Ссылка