Отримання знань

Задача Sheriff

(запропонована дільничним міліціонером)

У минулому  колгоспник, а тепер землевласник Наливайко одержав сертифікат на володіння землею. Сільрада видала йому схему ділянки. На схемі будинок мав координати в декартовій системі, а ділянка мала форму круга відомого радіуса, центр якого, природно, збігався з положенням будинку. Усе було б нічого, якби не сусідка Наливайко, знатна господиня, що мала дивну звичку натягати мотузки для сушіння білизни незважаючи ні на які межі, прив'язуючи кінці мотузки до чого завгодно. І ще одна дивина була у сусідки: мотузки завжди були натягнуті паралельно якійсь з осей тієї самої системи координат. Наливайко звернувся до мене зі скаргою, що мотузка проходить через його землеволодіння. Якої довжини відрізок мотузки дійсно проходив через землі Наливайка, якщо відомі координати її початку і кінця в  тій же системі координат?

Технічні умови: Програма читає з клавіатури в першому рядку два дійсних числа, розділених пропуском – координати центра круга, у другому рядку – дійсний радіус круга, у третьому – 4 дійсних числа, розділені пропуском – координати початку (х₁, y₁) і кінця (х₂, y₂) мотузки. Програма виводить на екран результат із точністю до 2-х знаків. Координати і радіус по модулю не більші 1000.00

Розв'язок задачі Sheriff

Розв'язок полягає в акуратному розгляді всіх можливих варіантів розміщення круга і відрізка. Щоб зменшити їх кількість, спочатку нормалізуємо дані: по-перше, якщо відрізок паралельний осі ординат, то поміняємо осі місцями; по-друге, якщо x1 < x2, то поміняємо місцями кінці відрізка. Якщо пряма, що містить відрізок, не перетинає круг, то і сам відрізок не перетинає його. Залишаються наступні варіанти:

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

                                            

 Тоді шукані точки будуть мати абсциси (L_x – ліва, R_x – права):

L_x = max(C_x – d,x1),

Rx = min (C_x + d,x2)

 І, нарешті, якщо відрізок перетинає круг, то відповіддю буде різниця R_x-L_x, якщо ж не перетинає – ця різниця буде від’ємною і шукана відстань рівна нулю.

Перевірити розв'язок задачі  Sheriff в режимі on-line