Polish version    English version  
  Historia OI -> XIII OI 2005/2006


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

Najazd

Limit pamięci: 32 MB

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:

  • ma kształt trójkąta, którego wierzchołkami są pewne trzy różne wierzchołki wielokąta-wyspy,
  • przyniesie im jak największe zyski, tzn. suma zysków i strat przynoszonych przez fabryki znajdujące się na opanowanym terytorium będzie możliwie jak największa.
Przyjmujemy, że jeżeli fabryka leży na brzegu lub w wierzchołku opanowanego terytorium, to należy do niego. Terytorium, które nie zawiera żadnej fabryki przynosi oczywiście zysk równy 0.

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.

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia opis kształtu Bajtocji i położenie fabryk,
  • wyznaczy 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.
  • wypisze wynik na standardowe wyjście.

Wejście

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.

Wyjście

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 -4
poprawną odpowiedzią jest:
5



Wersja do druku