|
Якось на Багатокутію напали Трикутники. Королівство Багатокутія лежить на острові і займає всю його територію. Острів має вигляд опуклого багатокутника (такого багатокутника, у якого кожен внутрішній кут менший від 180°). У Багатокутії знаходиться певне число фабрик програмного забезпечення. Кожна фабрика приносить певні постійні прибутки або збитки.
Трикутники вирішили заволодіти частиною площі Багатокутії, яка має наступні властивості:
• має вигляд трикутника, вершинами якого є три різні вершини багатокутника-острова;
• принесе їм якнайбільші прибутки, тобто сума прибутків (збитків), що приносять фабрики, які знаходяться на території, буде якнайбільшою.
Відомо, що якщо фабрика лежить на границі або у вершині території, якою заволоділи Трикутники, то вона належить їй. Територія, яка не містить жодної фабрики, приносить прибуток рівний 0.
Король Багатокутії вирішив порахувати, наскільки великі збитки для економіки країни може принести нашестя Трикутників. Допоможіть йому і напишіть програму, яка визначає суму прибутків (збитків), що дають фабрики, якими хочуть заволодіти Трикутники.
Формат вхідних даних
Перший рядок вхідного файлу містить одне ціле число n (3<=n<=600), число вершин багатокутника-острова.
В наступних n рядках записано по два цілих числа xj та yj - координати вершин багатокутника-острова у порядку його обходу за годинниковою стрілкою (-10000<= xj,yj<=10000), відокремлених одним пробілом.
В (n+2)-му рядку міститься одне ціле число m – число фабрик (1<=m<=10000), що розташовані на острові.
В наступних m рядках міститься по три цілих числа: x'i, y'i і wi (-10000<=x'i, y'i<=10000, -100000<=wi=0) або збиток (для wi<0), який фабрика приносить. Кожна фабрика лежить на острові-багатокутнику, тобто всередині його або на його границі (березі). Декілька фабрик можуть лежати в одному і тому ж місці, тобто мати ті самі координати.
Формат вихідних даних
Перший і єдиний рядок вихідного файлу повинен містити одне ціле число, що означає максимальну суму прибутків, які приносять фабрики, що знаходяться в межі трикутника, вершинами якого є три різні вершини багатокутника-острова. Може бути, що число це буде від’ємним.
Приклад
|
Island.DAT
|
Island.SOL
|
|
5
4 1
1 4
8 9
11 5
8 1
4
7 2 3
6 3 -1
4 5 3
9 6 -4
|
5
|
|
1. Перебрати всі трикутники опуклого многкутника
(три вкладених цикли
i=1..n-2
j=i+1 .. n-1
k=j+1.. n
для чотирикутника 1,2,3; 1,2,4; 1,3,4; 2,3,4)
2. Перевірити належність точок трикутнику перебравши всі точки
(перевірити можна за площою трикутників: якщо точка лежить в трикутнику то сума площ трьох трикутників утворених з даною точкою та вершинами тркутника рівна площі трикутника)
Формула площі трикутника за кординатами вершин:
S=1/2*|x1*y2-x2*y1+ x2*y3-x3*y2+ x3*y1-x1*y3|
|
