Четвертий тур

Розв’язки задач відправляти з 08.11 по 21.11.2010 р.

Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.

1. Задача river (20 балів)

Ім’я вхідного файлу: river.DAT

Ім’я вихідного файлу: river.SOL

Максимальний час роботи на одному тесті: 3с

Між двома королівствами Читанія та Писанія протікає річка Пряма, яка тече або з Півночі на Південь, або з Заходу на Схід. Король Писанії вирішив завоювати Читанію. Для нападу необхідно збудувати переправу.

Де розпочинати будівництво, якщо король хоче, щоб всі війська, що розташовані в N (1<=N<=100) гарнізонах, могли якнайшвидше зібратися біля переправи? Війська вирушають з пунктів дислокації одночасно і рухаються з однаковою швидкістю по прямій до переправи.

Формат вхідних даних

Перший рядок вхідного файлу містить чотири цілих числа: a₁, a_2, b₁, b₂ ((a₁,a₂), (b₁,b₂) – координати двох точок річки Прямої).

Відомо, що або a₁=b₁ , або a₂=b₂, -30000<=a₁, a_2, b₁, b₂ <=30000.

У другому рядку знаходиться ціле число N – кількість гарнізонів (1<=N<=100).

В наступних N рядках записано по два цілих числа x_j та y_j – координати гарнізонів

(-30000<= x_j,y_j<=30000), відокремлених одним пробілом.

Формат вихідних даних

Ваша програма повинна вивести у вихідний файл рядок, що містить два числа X, Y – координати переправи з точністю до двох знаків після коми, розділених одним пропуском.

Приклад

2. Задача Island (100 балів)

Ім’я вхідного файлу: Island.DAT

Ім’я вихідного файлу: Island.SOL

Максимальний час роботи на одному тесті: 5с

Якось на Багатокутію напали Трикутники. Королівство Багатокутія лежить на острові і займає всю його територію. Острів має вигляд опуклого багатокутника (такого багатокутника, у якого кожен внутрішній кут менший від 180°). У Багатокутії знаходиться певне число фабрик програмного забезпечення. Кожна фабрика приносить певні постійні прибутки або збитки.

Трикутники вирішили заволодіти частиною площі Багатокутії, яка має наступні властивості:

• має вигляд трикутника, вершинами якого є три різні вершини багатокутника-острова;

• принесе їм якнайбільші прибутки, тобто сума прибутків (збитків), що приносять фабрики, які знаходяться на території, буде якнайбільшою.

Відомо, що якщо фабрика лежить на границі або у вершині території, якою заволоділи Трикутники, то вона належить їй. Територія, яка не містить жодної фабрики, приносить прибуток рівний 0.

Король Багатокутії вирішив порахувати, наскільки великі збитки для економіки країни може принести нашестя Трикутників. Допоможіть йому і напишіть програму, яка визначає суму прибутків (збитків), що дають фабрики, якими хочуть заволодіти Трикутники.

Формат вхідних даних

Перший рядок вхідного файлу містить одне ціле число n (3<=n<=600), число вершин багатокутника-острова.

В наступних n рядках записано по два цілих числа x_j та y_j - координати вершин багатокутника-острова у порядку його обходу за годинниковою стрілкою (-10000<= x_j,y_j<=10000), відокремлених одним пробілом.

В (n+2)-му рядку міститься одне ціле число m – число фабрик (1<=m<=10000), що розташовані на острові.

В наступних m рядках міститься по три цілих числа: x'_i, y'_i і w_i (-10000<=x'_i, y'_i<=10000, -100000<=w_i<=100000), відокремлених одним проміжком і такі, що означають відповідно x'_i, y'_i – координати фабрик, а також прибуток (для w_i>=0) або збиток (для w_i<0), який фабрика приносить. Кожна фабрика лежить на острові-багатокутнику, тобто всередині його або на його границі (березі). Декілька фабрик можуть лежати в одному і тому ж місці, тобто мати ті самі координати.

Формат вихідних даних

Перший і єдиний рядок вихідного файлу повинен містити одне ціле число, що означає максимальну суму прибутків, які приносять фабрики, що знаходяться в межі трикутника, вершинами якого є три різні вершини багатокутника-острова. Може бути, що число це буде від’ємним.

Приклад