Island

Очень вас прошу...

2. Задача Island
Имя входного файла: Island.DAT
Имя выходного файла: Island.SOL
Максимальное время работы на одном тесте: 5с
Однажды на Багатокутию напали Треугольники. Королевство Багатокутия лежит на острове и занимает всю его территорию. Остров имеет вид выпуклого многоугольника (такого многоугольника, у которого каждый внутренний угол меньше 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 <= 100000), разделенных одним промежутком и такие , означающие соответственно x'i, y'i - координаты фабрик, а также прибыль (для wi> = 0) или убыток (для wi <0), который фабрика приносит. Каждая фабрика лежит на острове-многоугольнике, т.е. внутри его или на его границе (берегу). Несколько фабрик могут лежать в одном и том же месте, то есть иметь те же координаты.
Формат выходных данных
Первый и единственный строка выходного файла должна содержать одно целое число, обозначающее максимальную сумму доходов, которые приносят фабрики, находящиеся в черте треугольника, вершинами которого являются три различные вершины многоугольника-острова. Может быть, число это будет отрицательным.
На латинице

Миниатюры

   

0

Какие-то олимпийцы в этом году не только тупые, но и бестолковые, в сотый раз им объясняют: думайте своей головой, нет, всё равно им надо олимпиадную задачу запостить.

1

1

А де її включит???? (кнопку)..........

0