Олімпіади інформатика та ІКТ
Учитель інформатики Миколаївського НВК.
Завдання II етапу Всеукраїнської учнівської олімпіади з інформатики 2005 рік
Завдання 1. Правильний n-кутник.
В правильному n-кутнику провели декілька діагоналей, причому ніякі три не перетинаються в одній точці. На скільки частин діагоналі розбили n-кутник? Діагоналі задані номерами вершин n-кутника, які вони сполучають, всі вершини перенумеровані по порядку числами 1,…, n.
Завдання 2. Прямокутники.
На вісь Ох площини Оху поклали N прямокутників. Потрібно знайти координати вершин ламаної, що огинає цю множину прямокутників (див. малюнок)
Вхідні дані: Файл input.dat.
Перший рядок вхідного файлу містить ціле число N (0
Вихідні дані: Файл output.dat.
В перший рядок вихідного файлу виведіть кількість вершин шуканої ламаної. Далі вкажіть самі вершини в порядку не убування абсциси. Кожна вершина задається своїми координатами, записаними через пропуск в окремому рядку вихіідного файлу. Ніякі дві ланки ламаної не повинні лежати на одній прямій.
Приклад вхідного файлу
2
0 4 2
2 4 5
Приклад вихідного файлу
6
0 0
0 2
2 2
2 5
6 5
6 0
Завдання 3. Стратегія бомбування.
В деякій війні зіткнулися інтереси двох держав – називатимемо їх R і U. Держава R вирішила нанести серію бомбових ударів для поразки найважливіших стратегічних центрів держави U. Була складена карта U; для простоти на ній була введена прямокутна декартова система координат. Відомий список N найважливіших стратегічних центрів U (їх координати). R хоче уразити всі ці центри. Кожна бомба, виготовлена в R, характеризується потужністю в тротиловому еквіваленті. Якщо бомба має потужність М тонн в тротиловому еквіваленті, і вона скинута в точку (х, у), то вона вражає всі стратегічні центри, відстань від яких до точки (х, у) не перевищує квадратного кореня з М. R хоче скинути на територію U три бомби. Відомі координати (х1, у1), (х2, у2), (х3, у3) точок, в які скинуті ці бомби.
Завдання.
Визначте, яку мінімальну сумарну потужність в тротиловому еквіваленті повинні мати скинуті бомби, щоб з їх допомогою можна було знищити всі стратегічні центри U?
Ввід.
Перший рядок вхідного файлу містить число N. Наступні N рядків містять координати стратегічних центрів U; координати кожного центру – в окремому рядку. Наступні 3 рядки містять числа х1, у1, х2, у2, х3, у3 по два числа в рядку.
Вивід.
Ваша програма повинна вивести у вихідний файл одне число – мінімальну сумарну потужність скинених бомб. Це число повинне бути виведено з точністю до двох знаків після коми.
Приклад.
Input.txt
4
0 0
0 2
2 0
2 2
3 0
3 3
0 3
output.txt
10.00
В даному прикладі можна скинути в точку (3, 0) бомбу потужністю 9.00 тонн, в точку (3, 3) – потужністю 0.00 тонн, в точку (0, 3) – потужністю 1.00 тонн.
Обмеження.
1≤N≤100; всі решта чисел при введенні – натуральні, що не перевищують 1000.
Powered by CuteNews
