Шостий тур
Розв’язки задач відправляти з 05.11 по 18.12.2011р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
1. Задача POINT (20 балів)
Ім’я вхідного файлу: POINT.DAT
Ім’я вихідного файлу: POINT.SOL
Максимальний час роботи на одному тесті: 1с
Багатокутник (не обов'язково опуклий) на площині заданий координатами своїх вершин. Потрібно підрахувати кількість точок з цілочисельними координатами, що лежать всередині нього (але не на його межі).
Формат вхідних даних
У першому рядку міститься N (3 <= N <= 1000) - число вершин багатокутника. У наступних N рядках йдуть координати (Xi, Yi) вершин багатокутника в порядку обходу за годинниковою стрілкою. Xi і Yi - цілі числа, по модулю не перевищують 1000000.
Формат вихідних даних
У вихідний файл вивести одне число - шукану кількість точок.
Приклади:
POINT.DAT
|
POINT.SOL
|
4
-1 -1
-1 1
1 1
1 -1
|
1
|
3
0 0
0 2
2 0
|
0
|
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 має містити дві пари чисел – координат двох точок, що однозначно задають розділення (пряму) з найменшим дефектом. Числа потрібно виводити у порядку: x1 y1 x2 y2. Координати потрібно виводити з точністю 10-3. Координати точок мають бути додатні та не більші за 1000.
Приклад вхідних та вихідних даних
polygon.DAT
|
polygon.SOL
|
3
2 1
3 3
4 1
3
5 2
3 2
4 3
|
2 5 4 1
|
|