прямої) частину менше правої (верхньої). Пряма ж, проходить через обрану точку і другу з фіксованих, ділить царство в зворотному співвідношенні. Тоді шукана точка знаходиться між двома фіксованими і її можна шукати шляхом розподілу навпіл. Тепер слід підрахувати кількість селищ в кожній з вже рівних за площею частин. Якщо воно різне, то на кордоні потрібно вибрати ще одну точку, при діленні царства за допомогою якої кількість селищ в половинах також буде співвідноситися по-іншому. Тепер можна застосувати метод розподілу навпіл для правильного вибору опорної точки.
Задача 4. Рандеву. ( VII Всеросійська олімпіада з інформатики. )
Локатори дальньої космічного зв'язку помічають летить в площині орбіти землі невідомий астероїд з координатами ( x , y ). Астероїд летить з постійною швидкістю, векторне значення якої дорівнює ( V x , V y ). Із землі з точки з координатами (0, 0) негайно стартує ракета з радіусом дії R ( R > 0). Ракета летить по прямій з постійною швидкістю в межах від 0 до W .
Потрібно визначити, чи може ракета підлетіти впритул до астероїда в межах радіусу її дії і знайти вектор швидкості ракети, при якому час зустрічі ракети з астероїдом мінімальне.
Результат розв'язання задачі повинен бути обчислений з похибкою не більше 0.01. Впливом землі і всіх космічних об'єктів знехтувати. Ракета і астероїд рухаються в одній площині. p> На початку вхідного файлу міститься число N - кількість наборів вихідних даних (тестів). Далі розташовані N наборів вихідних даних; кожен набір - шість речових чисел: X , Y , V x , V y , W , R . Всі числа в початковому файлі розділяються пробілами і (або) символами перекладу рядка.
Для кожного набору вихідних даних вивести з нового рядка вектор швидкості ( U x , U y ) і мінімальний час до зустрічі, або повідомлення "Зустріч неможлива".
Приклад файлу вихідних даних
Приклад вихідного файлу
2
5.3 2.8 10.6 5.6 11.0 50.0
3.0 -4.0 -3.0 4.0 5.0 10.0
Зустріч неможлива
3.0 -4.0 0.5
В
Рішення. Для вирішення цього завдання перш за все необхідно вміти визначати взаємне розташування прямої, уздовж якою рухається астероїд, і кола з центром на Землі і радіусом R . Якщо вони не перетинаються, то зустріч неможлива, в іншому випадку потрібно відшукати точки їх перетину. Потім для пошуку точки зустрічі з мінімальним часом можна знову ж застосувати дихотомію.
3. Різні завдання
В
Задача 5. "Куди йдемо ми з П'ятачком? "( Кіровське відкрите командна першість з програмування, 2001 р.)
П'ятачок і Вінні-Пух щоранку ходять пити чай в гості до Кролика. Природно, самим коротким шляхом. На жаль, одного разу Вінні-Пуху прийшла в голову ідея вирити пастку для Слонопотама. Найприкріше, що вони з Пацем її навіть вирили. Тому тепер щоранку, йдучи в гості до Кролика, вони бояться в неї провалитися. p> Напишіть програму, яка порахує довжину найкоротшого безпечного шляху від будиночка Вінні-Пуха до будиночка Кролика. p> Пастка для Слонопотама являє собою яму абсолютно круглої форми. Шлях є безпечним, якщо він не проходить по пастці (але може проходити по її кордоні).
У вхідному файлі записані спочатку координати будиночка Вінні-Пуха X В Y В , потім - координати будиночка Кролика X К Y К , а потім - координати центру і радіус пастки X Л Y Л R Л . Усі координати - цілі числа з діапазону від -32000 до 32000. Радіус пастки - натуральне число, не більше 32000.
Будиночки Вінні-Пуха і Кролика не можуть перебувати всередині пастки, але можуть перебувати на її кордоні.
Виведіть у вихідний файл одне число - довжину найкоротшого безпечного шляху від будиночка Вінні-Пуха до будиночка Кролика з трьома знаками після крапки.
Приклади вхідного файлу
Приклади вихідного файлу
0 0 0 1 10 10 1
1.000
5 0 0 5 0 0 5
7.854
-5 0 5 0 0 0 3
11.861
В
Рішення. Для вирішення цього завдання необхідно визначати взаємне розташування кола і відрізка (а не прямий!) і правильно обчислювати довжину дуги кола, обмеженою двома заданими точками.
Задача 6. Підсвічува...
