Вказівки щодо розв'язання завдання № 2
відбірково-тренувальних зборів команди міста Києва

2.1. Мотель (аналітична геометрія)

  1. Знайти коефіцієнти загальних рівнянь прямих.

  2. Знайти різні точки перетину пар прямих з урахуванням того, що різні пари прямих можуть перетинатися в одних і тих самих точках.

  3. Знайти суму відстаней до даних прямих для знайдених точок перетину пар прямих.

  4. Якщо мінімум суми відстаней досягається в одній точці, то шукана множина містить лише її.

  5. Якщо мінімум суми відстаней досягається у двох точках, то шукана множина є відрізком, що їх сполучає.

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

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

2.2. Тест (робота з двовимірними масивами)

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

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

  3. Для кожної пари фігур фігури порівнюємо лише за умови, що вони мають однакові кількості клітин і габарити. Якщо фігури можна сумістити одним з таких восьми способів:

    • паралельним переносом;
    • паралельним переносом і симетрією відносно горизонтальної прямої;
    • паралельним переносом і симетрією відносно вертикальної прямої;
    • паралельним переносом і поворотом на 180°;
    • паралельним переносом і поворотом на 90°;
    • паралельним переносом і поворотом на 270°;
    • паралельним переносом, поворотом на 90° і симетрією відносно горизонтальної прямої;
    • паралельним переносом, поворотом на 270° і симетрією відносно горизонтальної прямої,

    то виключаємо фігуру з більшим номером з переліку різних фігур.