Сайт підготовки до олімпіади з інформатики

ема. КОМБІНАТОРНІ ОБ'ЄКТИ

Тема. Комбінаторні задачі

Комбінаторика - розділ математиків, в якому вивчаються найпростіші «з'єднання» чисел.

1) Формули комбінаторики

Задачі:

1.        Скількома способами можна скласти розклад на день з  5 різних предметів, якщо в класі вивчається 10 предметі?

2.        Скільки різних чотирицифрових чисел можна скласти з чотирьох різних заданих цифр, не повторюючи їх?

3.        Скільки діагоналей має опуклий n-кутник?

1.Перестановки - з'єднання, які можна скласти з  n предметів, міняючи всіма можливими способами їх порядок.

Pn=n!

2.Розміщення - з'єднання, що містять по  n предметів з числа  m даних, що розрізняються або порядком предметів, або самими предметами.

An,k=n!/(n-k)!

3. Комбінації - з'єднання, що містять по  n предметів з  m, що розрізняються один від одного, принаймні, одним предметом.

Cn,k=n!/((n-k)!k!)

Додаткові завдання:

1. Скількома способами можна розподілити n тем наукових робіт серед m учнів (тем більше, ніж учнів). Написати програму.

2. Перевірити справедливість рівності C0,k+c1,k+...+Ck.k=2^k для m<10.

3. Скількома способами можна розмістити n осіб за столом, біля якого поставлено nстільців?  Написати програму.

4. Двоє хлопчиків Роман і Діма мають по N друзів (1<=N<=200). Вирішили вони позмагатися хто з них більше організує вечірок. Роман вирішив запрошувати кожен раз до себе в гості по K(1<= K<= N) друзів, а Діма - по М (1<= М<= N) друзів. Хто з хлопчиків більше організує вечірок і на скільки, якщо вони домовились, що кожен раз компанія має бути іншою.

Наприклад.

Якщо є четверо друзів (1, 2, 3, 4) і вони мають приходити в гості по троє, то таких вечірок буде чотири ( (1, 2, 3); (1, 2, 4); (1, 3, 4); (2, 3, 4) ).

5. Скількома способами можна вибрати делегацію в складі n представників з m чоловік. Написати програму.

6. Побудувати трикутник Паскаля з n рядків

1

1 2 1

1 3 3 1

.....

Робота з файлами

1. Масиви

1. Дано масив A[1..15]. Скласти програму заміни всіх його  елементів, що більші 10 на нулі.

2. Дано лінійну таблицю  із  n  дійсних  чисел.  Знайти  суму  S  всіх додатних елементів.

3. В таблиці а[1..100)]всі елементи рівні 2,3,4 або 5. Написати  програму, яка заміняє 2 на 5, 3 на 4, 4 на 3, 5 на 2.

4. Скласти програму підрахунку суми елементів з непарними номерами  масиву A[1..25].

5. Дано  масив  A[1..2N].  Скласти  програму   знаходження   різниці   сум елементів першої та другої половини масиву.

6.  Дано  лінійну  таблицю  із  n  дійсних  чисел.  Замінити  від`ємні елементи їх квадратами.

7. Задано таблиця A[1..N]. Побудувати таблицю  B[1..N],  в  якій  першими розміщені всі від`ємні елементи таблиці A, а потім всі додатні.

8. Із елементів масиву (a1,a2,...,a20) складіть масив B, елементи якого по модулю більші деякого значення С(|a|>c).

9. Дано натуральна таблиця A[1..10]. В таблицю М записати тільки ті числа, остача від ділення яких на 3 рівна 1, а на 5 рівна 2.

10. Провірити, чи є в одномірному числовому масиві  хоча  б  одна  пара сусідніх чисел, які ї протилежними.

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

12. Визначити в одномірному числовому масиві число сусідства із двох чисел різного знаку.

13. Для заданого масиву A(N) знайти  суму  всіх  елементів,  не  більших заданого числа N.

14. Дано масив A[1..M]. Скласти програму перестановки місцями елементів з  парними та непарними номерами.

15. Визначити в одномірному числовому масиві суми додатних і  від`ємних елементів.

16. Провірити, чи ї в даному одномірному числовому масиві хоча  б  одна пара чисел, які співпадають по величині.

17. Скласти програму запису в таблицю квадратів чисел від 1 до 100.

18. Даний одномірний  числовий  масив.  Визначити  суму  добутків  всіх трійок сусідніх чисел.

19. Скласти  програму  підрахунку  кількості  мінімальних  елементів  в масиві A[1..N].

20.В одномірному числовому масиві всі від`ємні елементи замініть  нуля ми.

21. Провірити, чи є одномірний числовий масив упорядкованим по зростанню.

22.  Дано  натуральний  масив  A[1..N].Скласти  програму  підрахунку  парних елементів цього масиву.

23. Дано лінійний масив A[1..M].Скласти програму заміни елементів з  непарними номерами на їх квадрати.

24. Скласти програму заміни в прямокутному масиві A[1..k] всіх елементів, що більші від 10 на нулі.

25. Дано нат таб A[1..20]. В таблицю М записати тільки ті числа, остача від ділення яких на 3 рівна 1.

26.  Визначити  в  одномірному  числовому  масиві  число   сусідств   з взаємо-обернених чисел.

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

29. Даний одномірний  числовий  масив.  Визначити  суму  всіх чисел.

2.Масиви (Серйозні розважалки)

1. Барон Мюнхаузен, вийшовши на екологічно чисте по­лювання, зарядив свою рушницю кісточками вишень. Після того як він вдало влучив поміж роги оленям, в яких влучило відповідно k₁,k₂,…,k_N кісточок, у них на головах виросли чудові молоді вишеньки. Скільки нових саджанців зміг подарувати барон Мюнхаузен садівникам-дослідникам?

2. Мама розвела оранжерею кактусів, деякі з яких були колючі, а інші — ні. Маленька донечка Яринка вирішила, що голки на кактусах — це надто зухвало, і тому старанно поголила їх бритвою. Добре, що у мами залишився записник, в якому всі кактуси були позначені кількістю голочок α₁,α₂,…, α_N (голі кактуси були позначені 0). Скількох кактусів не торкнулася рука юної перукарки?

3. Середню групу дитячого садочка вивели на прогулянку. Скільки дівчаток і скільки хлопчиків видно з-за паркану, якщо зріст хлопчиків задається у сантиметрах від'ємними числами, а дівчаток — додатними у вигляді цілих значень α₁,α₂,…, α_N ? Окрім того, у всіх дівчаток на голівках зав'язані бантики заввишки 10 см, а висота паркану H см.

4. Маленький онучок вирішив допомогти бабусі підстригти квіти у її дорогоцінному квітнику, зрізавши лише бутони та квіточки на них. На щастя, кмітливий хлопчик зрізав лише ті квіти, які були заввишки від h₁ см до h₂, см від землі. Скільком квіточкам пощастило бути підстриженими, якщо висота їх у сантиметрах становить α₁,α₂,…, α_N ?

5. Коли барон Мюнхаузен вирішив пообідати, він прив'язав до довгої мотузки шматок сала і закинув його у повітря. Зграя диких гусей, що пролітала тим часом над помешканням барона, заціка­вилася незвичним предметом і найстарший гусак, що очолював зграю, проковтнув його. Не встиг він насолодитися відчуттям ситості, як шматок сала проскочив через нього і зник у дзьобі другого гусака і т.д. Тепер доля обіду барона Мюнхаузена залежала лише від довжини мотузки! Скільки кілограмів підсмаженої гусятини було подано на обід барона Мюнхаузена, якщо довжина мотузки становила L см, N гусей летіли на відстані h см один від одного, довжина кожного з них дорівнює k см, а вага цих гусей у кілограмах становила m₁,m₂,…,m_N ?

6. Маленький Дмитрик щомісяця виростає на 2 cм, а у бабусі в комірчині облаштовано полички з різними ласощами — варенням, джемом, повидлом. Акуратистка бабуся записувала висоту і наступний порядковий номер у свій записник кожної нової полички в тій послідовності, як вона з'являлася у комірчині завдяки дідусеві. Висота цих поличок була а1, а2, ... аN, см. Нові полички дідусь прибивав, де йому заманеться — вище, нижче і між тими, що вже були. З'ясувати, через скільки місяців до яких поличок, враховуючи їх порядок запису в бабусиній книжці, добереться Дмитрик (наприклад, спочатку до п'ятої, занотованої у записнику, потім до другої і т.д.), якщо він відкрив для себе бабусину комірчину, коли його зріст був Н1 см, а доросте Дмитрик до H2 см.

7. Велосипедист-початківець Павлуша виїхав на широку дорогу. Але їхати інакше, ніж за законом синусоїди, йому ніяк не вдавалося. Юний спортсмен стартував у точці Х0 на осі ОХ, а центри основ стовпів знаходяться у точках х1,х2,...,хn на цій же осі, яку перетинає синусоїда руху велосипедиста. Скільки стовпів трапляться на шляху Павлуші, якщо шириною стовпа можна знехтувати?

8. Завзятий водій Василь Іванович вирішив поставити рекорд пе­регонів між містом Мляшем та містом Пляшем. Спочатку він придбав карти розташування заправок пальним на шляху між Мляшем та Пляшем, де відстань між заправками була позначена числами а1,а2,...,аN а потім побився об заклад зі своїми друзями, що вста­новить рекорд за Т год. Одна проблема турбувала Василя Івановича: об'єм бака для пального складав К л, а запасної каністри у нього не було. Витрати пального в дорозі становили 1л на 10 км шляху. Для еко­номії часу Василь Іванович на кожній заправці визначав, чи варто вит­рачати 10 хв. на дозаправку, чи можна доїхати до наступної заправки на залишках пального у баці. Чи зможе Василь Іванович встановити рекорд, якщо перша заправка знаходиться у місті Мляші, остання — у місті Пляші, а сам Василь Іванович їде зі сталою швидкістю ν км/год? Чи може таке статися, що Василь Іванович взагалі не доїде до міста Пляша?

9. Лікар-психіатр призначив Сергійкові лікування від лайливих слів. Виконуючи поради психіатра, хворий повинен був записувати у таблицю по днях упродовж місяця кількість використаних ввічливих слів «Дякую», «Пробачте», «Прошу». У який день місяця друзям Сергійка повезло на ввічливі слова найбільше? Якого дня місяця у хлопчика був найгірший настрій? Які ввічливі слова Сергійкові найбільше до вподоби?

3. Масиви. Вправи та задачі

1. Обчисліть значення b[l,l]+b[l,2]+b[l,3]+b[l,4] у масиві оцінок b.

2. Обчисліть b[l,l]+b[2,l]+b[3,l]+b[4,l]+b[5,l] у масиві оцінок b.

3. Обчисліть s:=0; for i:=l to 4 do s:=s+b[2,i] у масиві оцінок b.

4. Обчисліть s:=0; for i:=l to 5 do s:=s+b[i,l] у масиві оцінок b.

5. Запишіть команди для виведення значень двовимірного масиву оцінок b у вигляді таблиці.

6. Запишіть команду опису типу масиву цілих чисел з чотирма рядками і трьома стовпцями і оголосіть два такі масиви.

7. Запишіть команду присвоєння, якою елементові масиву, що є на перетині третього рядка і четвертого стовпця, можна надати значення 7.

8. Запишіть команди для збільшення значень усіх елементів двовимірного масиву b на одиницю.

9. Обчисліть суму всіх елементів двовимірного масиву b.

10. Побудуйте двовимірний масив з п'ятьма рядками і п'ятьма стовпцями за формулою d.. ·= sin(/+/); i=l,2,...,5; j = 1,2, ...,5. Виведіть масив на екран у вигляді таблиці. Задайте формати виведення чисел з двома цифрами після крапки; намагайтеся, щоб таблиця виглядала якнайкраще.

11. Див. умову задачі 10. У масиві d обчисліть суму додатних елементів.

12. Див. умову задачі 10. У масиві d обчисліть добуток елементів більших, ніж 0,5.

13. Див. 10. У масиві d визначіть максимальний елемент та його індекси.

14. Див. умову задачі 10. У масиві d від'ємні елементи замініть нулями. Скільки є додатних елементів?

15. Див. 10. У масиві d поміняйте місцями перший і останній стовпці.

16. Див. 10. У масиві d обчисліть суму елементів під головною діагоналлю (i<j).

17. Див. умову задачі 10. У масиві d обчисліть середньоарифметичні значення елементів кожного рядка.

18. Див. 10. У масиві d максимальний елемент поміняйте місцями з мінімальним.

19. Проект «Моя сім'я». Дані для розв'язування цієї задачі потрібно підготувати у вигляді таблиць заздалегідь. Нехай k — це кількість членів вашої сім'ї. В одновимірний сталий масив В уведіть імена чи статус членів сім'ї (я, батько, мати, брат тощо). Заповніть сталий двовимірний числовий масив А, що має k рядків і чотири стовпці, такою інформацією у стовпцях: 1 - номер за порядком члена сім'ї, 2 - рік народження, 3 - зріст у см, 4 -розмір одягу. Виведіть таблиці для огляду на екран. Складіть програму, щоб відповісти на запитання:

а) чи носите ви одяг 46-го розміру;

б) хто носить плащ 50-го розміру;

в) у кого зріст понад 170 см;

г) скільки років члену сім'ї, що є другим у списку;

д) кому можна переглядати фільми для дорослих; е) хто в сім'ї найвищий?

20. Проект «Наші оцінки». Задано текстову лінійну таблицю T, n елементів якої - це прізвища учнів вашого класу, а також числову прямокутну

таблицю В, n*m елементів якої - це оцінки учнів з певного предмета за деякий час навчання (m - максимальна кількість оцінок одного учня). Перший стовпець у таблиці В - оцінки за контрольну роботу. Щоб таблиця В була заповненою, вважатимемо, що, крім оцінок, вона містить такі числові дані: -1 (учень відсутній), 0 (учень присутній, але не опитаний). Виконайте завдання:

а) дані з таблиць занесіть у сталі масиви і виведіть три списки учнів, які отримали за контрольну роботу 10, 11, 12 балів;

б) який середній бал за контрольну роботу в класі;

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

г) розгляньте пункт в) і випадок, коли середня оцінка має дробову час­тину 0,5. Тоді заокруглення виконайте у бік більшого значення за умови, що остання оцінка виІца від середньої;

д) проаналізуйте відвідування учнями уроків з конкретного предмета. Скільки пропусків має кожен учень? Скільки це у відсотках? Який середній відсоток відвідування учнями уроків з цього предмета?

е) об'єднайте всі завдання в одну програму (використайте підпрограми). Дайте свої пропозиції щодо вдосконалення (розширення можливостей) отриманого алгоритму.

Робота з масивами

Завдання олімпіади з інформатики

Максимальна кількість балів – 100. 5 завдання по 20 балів кожне.

Вхідні дані допускається читати як з клавіатури (консолі), так і з файлу input.txt, вихідні данні необхідно виводить на екран (в консоль), або в файл output.txt.

Задача 1. «Дільники» (20 балів)

Вводяться два числа  N і K. Виведіть кількість чисел з діапазону від 1 до N таких, щоб їх сума цифр ділиться на K.

Задача 2. «Трикутники» (20 балів)

На площині дано N точок. Ніякі дві точки не співпадають. Знайдіть трикутник з вершинами в цих точках, що має найменший можливий периметр.

Введення

Спочатку вводиться число N - кількість точок (3 ≤ N ≤ 50), а потім N пар дійсних чисел, які задають координати точок.

Виведення

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

Задача 3. «Драбинка» (20 балів)

Драбинкою називається набір кубиків в один або декілька шарів, в якому кожен вищий верхній шар містить кубиків менше, ніж нижній.

Підрахувати число драбинок, котре можна побудувати з  N кубиків.
Введення
На вході записано число N (1 ≤ N ≤ 100).

Виведення
Вивести шукане число драбинок.

Задача 4. «Віруси» (20 балів)

На полі розміром N * N розташоване M вірусів. За кожен хід вірус заражає 4 сусідні з ним клітини. Положення вірусів задано координатами на полі. Потрібно написати програму, що визначає, за яке найменшу кількість ходів буде заражене все поле.

Введення

У першому рядку записано два числа N (1 ≤ N ≤ 100) та M (1 ≤ M ≤ 10). Кожний з наступних M рядків містить по два числа - координати вірусу на полі. Всі числа цілі, координати за величиною не перевершують розмірів поля. Ліва нижня клітинка поля має координати (1, 1).

Виведення

В перший і єдиний рядок виведіть одне число - шукану найменшу кількість ходів.

Задача 5. «Гра» (20 балів)

Легендарний вчитель математики Юрій Петрович придумав забавну гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів і одиниць, що починається з одиниці. (Наприклад, десяткове число 19₁₀ = 1*2⁴+0*2³+0*2²+1*2¹+1*2⁰ в двійковій системі запишеться як 10011₂.) Потім учитель починає зсув цифр отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі інші зсуваються на одну позицію вправо), виписуючи утворюються при цьому послідовності з нулів і одиниць у стовпчик - він помітив, що незалежно від вибору початкового числа виходять послідовності починають з деякого моменту повторюватися. І, нарешті, Юрій Петрович відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом пророблених маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

...

і результатом гри, отже, опиниться число 1*2⁴+1*2³+1*2²+0*2¹+0*2⁰ = 28. Оскільки придумана гра з числами все більше займає уяву вчителя, відволікаючи тим самим його від роботи з дуже обдарованими школярами, Вас просять написати програму, яка б допомогла Юрію Петровичу отримувати результат гри без утомливих ручних обчислень.

Введення

Введення містить одне ціле число N (0 ≤ N ≤ 32767).

Виведення

Ваша програма повинна вивести одне ціле число, рівне результату гри.

Розв'язуйте і відправляйте задачі

реєстрація в школі

задачі

відправити розв'язок

скачати матеріали

Успіхів та перемог !!!

(ДИВИСЬ ВКЛАДЕНИЙ ФАЙЛ)

Визначення площі довільного многокутника

За заданими координатами вершин многокутника визначити його площу.

Для обчислення площі можна використати формулу:

S=1/2*abs((x1*y2-x2*y1)+ (x2*y3-x3*y2)+..+ (xn*yn+1-xn+1*yn)), xn+1=x1; yn+1=y1.

Побудова опуклої оболонки для множини з N точок площини

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

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

(ДИВИСЬ ВКЛАДЕНИЙ ФАЙЛ)

Задача 10. Task10 . Багатокутник на площині задано цілочисельними координатами своїх N вершин у декартовій системі координат. Потрібно знайти площу многокутника. Сторони багатокутника не стикаються (за винятком сусідніх - у вершинах) і не перетинаються.

введення

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

виведення

Вивести одне число - площа багатокутника. Його слід округлити до найближчого числа з однією цифрою після десяткової крапки.

обмеження

3 ≤ N ≤ 50 000, координати вершин цілі і по модулю не перевищують 20000.

Задача11.task11. Нова держава.

Іваном Річкоплавцем і його командою був відкритий новий багатий континент, який назвали Іванія, де вони вирішили оселитися. Кожним членом команди було засноване нове поселення і назване його іменем. Їхні нащадки вирішили утворити нову державу і побудувати кордон, таким чином щоб границя була мінімальної довжини у вигляді прямих відрізків, які з’єднають поселення, біля яких пройде кордон при умові, що в середині будуть всі інші поселення і площа країни буде найбільшою. Яка довжина границі утвореної держави і її площа?

Вхідні дані

В першому рядку знаходиться натуральне N (3<=N<=50) – число поселень. В наступних рядках координати кожного поселення X,Y, які записуються через пропуск. X,Y – цілі числа (-1000<=X<=1000; -1000<=Y<=1000).

Вихідні дані

В першому рядку Р, а в другому S. P i S – дійсні числа із виведеними двома розрядами після коми.

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

Трикутник

Трикутник – 1) багатокутник із трьома сторонами; 2) це фігура, що складається з трьох точок, які не лежать на одній прямій, та трьох відрізків, які сполучають попарно ці точки. Відрізки називають сторонами трикутника, а точки – вершинами трикутника.

Бісектриса трикутника – відрізок бісектриси кута, що з'єднує вершину трикутника з точкою протилежної сторони. Довжину бісектиси трикутника, ака проведена до сторони a, можна знайти за формулою la=2/(a+b)*sqrt(b*c*p*(p-1)), p=(a+b+c)/2

Медіана трикутника – відрізок, який з'єднує вершину трикутника з серединою протилежної сторони. Довжину медіани трикутника, ака проведена до сторони a, можна знайти за формулою ma=sqrt(2*a^-+2*c^2-a^2)

Висота трикутника – перпендикуляр, проведений із вершини трикутника до прямої, що містить протилежну сторону. Довжину висоти трикутника, ака проведена до сторони a, можна знайти за формулою:ha=2s/a.

Периметр трикутника p=a+b+c; a=sqrt((x2-x1)^2+(y2-y1)^2); b=sqrt((x3-x2)^2+(y3-y2)^2); c=sqrt((x1-x3)^2+(y1-y3)^2).

Площа трикутника дорівнює півдобутку сторони на висоту, проведену до цієї сторони:Формула: S=a*h/2                

Площа трикутника дорівнює півдобутку сторін на синус кута між ними:Формула: S=b*c*sin(α)/2

Площа трикутника (формула Герона) дорівнює Формула: S=sqrt(p*(p-a)*(p-b)*(p-c)),p=(a+b+c)/2

Площа трикутника (векторний добуток) s=1/2|(x1*y2-x2*y1)+(x2*y3-x3*y2)+(x3*y1-x1*y3)|

Радіус кола, описаного навколо трикутника: Формула: r=abc/4S

Радіус кола, вписаного в трикутник:Формула: r=S/p

Теорема косинусів Квадрат будь-якої сторони трикутника дорівнює сумі квадратів двох інших сторін без подвоєного добутку цих сторін на косинус кута між ними.Формула: a^2 = b^2 + c^2 - 2*b*c*cos(alpha)

Теорема синусів Сторони трикутника пропорційні синусам протилежних кутів.Формула: a/sin(alpha) = b/sin(beta) = c/sin(gamma)

Теорема Піфагора. У прямокутному трикутнику квадрат гіпотенузи дорівнює сумі квадратів його катетів, тобто c^2 = a^2 + b^2

Задачі

Рівень 1

1.За заданими сторонами обчислити периметр трикутника.

2. За заданими координатами точок обчислити периметр трикутника.

3. За заданими сторонами обчислити площу трикутника.

4. За заданими координатами точок обчислити площу трикутника.

5. За заданими сторонами перевірити чи є трикутник рівностороннім.

6.  За заданими сторонами перевірити чи є трикутник рівнобедреним.

7.  За заданими координатами точок визначити чи є трикутник прямокутним.

8. Перевірити існування трикутника з заданими сторонами.

Рівень 2

1. За заданими координатами вершин трикутника обчислити його висоти.

2. Трикутник на площині задається цілочисельними координатами вершин. Для заданої точки Z(x,y) визначити,  чи належить вона стороні трикутника чи лежить усередині чи поза ним.

3. В межах міста, границя якого відома, а будинки задані своїми координатами, потрібно вибрати місце для будівництва хімічного заводу так, щоб відстань від нього до найближчого будинку була максимальною. Фактично нам потрібно знайти коло з максимальним радіусом, яке не має всередині точок з початкової множини, центр якого лежить всередині або на границі заданої ламаної.

4. За координатами будівель міста підібрати місце для будівництва культурного центру так, щоб відстань до максимально віддаленого від нього будинку була мінімальною.

Додатковий матеріал

1. Структура розгалуження С++

2. Обчислювальна геометрія (Омелян П.П.)