Stało się - Trójkątowie najechali Bajtocję!
Bajtocja leży na wyspie i zajmuje całą jej powierzchnię.
Wyspa ta ma kształt wielokąta wypukłego
(tzn. takiego wielokąta, którego każdy
kąt wewnętrzny jest mniejszy od ).
W Bajtocji znajduje się pewna liczba fabryk oprogramowania.
Każda fabryka przynosi pewne stałe zyski lub straty.
Trójkątowie postanowili opanować taki fragment Bajtocji, który:
Król Bajtocji, Bajtazar, zastanawia się, jak duże straty dla gospodarki kraju może przynieść najazd Trójkątów. Pomóż mu i napisz program, który wyznaczy sumę zysków i strat przynoszonych przez fabryki, które chcą opanować Trójkątowie.
Napisz program, który:
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą
(
), oznaczającą liczbę wierzchołków
wielokąta-wyspy.
Kolejnych
wierszy wejścia zawiera po dwie liczby całkowite
i
(
),
oddzielone pojedynczym odstępem i oznaczające współrzędne
i
kolejnych wierzchołków wyspy, podane w kolejności
zgodnej z kierunkiem ruchu wskazówek zegara.
Wiersz
-gi zawiera jedną liczbę całkowitą
(
), oznaczającą liczbę fabryk.
Kolejne
wierszy zawiera po trzy liczby całkowite
,
i
(
,
),
oddzielone pojedynczymi odstępami i oznaczające odpowiednio:
współrzędne
i
-tej fabryki, oraz zysk (dla
)
bądź stratę (dla
), którą ta fabryka przynosi.
Każda fabryka leży na wyspie-wielokącie, tzn.\ wewnątrz
niej lub na jej brzegu. Kilka fabryk może leżeć w tym samym miejscu, tj.
mieć te same współrzędne.
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą maksymalną sumę zysków i strat przynoszonych przez fabryki znajdujące się w obrębie trójkąta, którego wierzchołkami są pewne trzy różne wierzchołki wielokąta-wyspy. Może się zdarzyć, że liczba ta będzie ujemna.
Dla danych wejściowych:5 4 1 1 4 8 9 11 5 8 1 4 7 2 3 6 3 -1 4 5 3 9 6 -4poprawną odpowiedzią jest:
5