Шостий тур

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

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

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

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

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

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

Багатокутник (не обов'язково опуклий) на площині заданий координатами своїх вершин. Потрібно підрахувати кількість точок з цілочисельними координатами, що лежать всередині нього (але не на його межі).

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

У першому рядку міститься N (3 <= N <= 1000) - число вершин багатокутника. У наступних N рядках йдуть координати (Xi, Yi) вершин багатокутника в порядку обходу за годинниковою стрілкою. Xi і Yi - цілі числа, по модулю не перевищують 1000000.

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

У вихідний файл вивести одне число - шукану кількість точок.

Приклади:

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

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

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

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

На площині задано дві фігури, що обмежені опуклими багатокутниками. Фігури розташовані таким чином, що їх вершини не співпадають, а контури мають рівно 2 точки перетину.

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

Наприклад, на рисунку зображена пряма, що задає певне розділення багатокутників. Оцінка дефекту цього розділення (два випадки відповідності): (D)+(C+E) та (A+D)+(B+C). З рисунку, D+C+E менше, отже, загалом, оцінка розбиття дефекту розділення утвореного цією прямою є D+C+E.

Завдання

Напишіть програму polygon, що за заданими двома багатокутниками знаходить пряму, що утворює розділення з найменшим дефектом.

Вхідні дані

Перший рядок вхідного файлу polygon.DAT містить одне ціле число N (3<=N<=20) – кількість вершин першого багатокутника. Наступні N рядків містять пари цілих чисел – координати вершин першого багатокутника у порядку обходу. (N+2)-й рядок файлу містить число M (3<=M<=20) – кількість вершин другого багатокутника. Наступні M рядків містять його координати задані таким же чином, як і для першого багатокутника. Координати точок додатні та не перевищують 1000.

Вихідні дані

Єдиний рядок вихідного файлу polygon.SOL має містити дві пари чисел – координат двох точок, що однозначно задають розділення (пряму) з найменшим дефектом. Числа потрібно виводити у порядку: x₁ y₁ x₂ y₂. Координати потрібно виводити з точністю 10^-3. Координати точок мають бути додатні та не більші за 1000.

Приклад вхідних та вихідних даних