Задача тижня 26.11.12 – 02.12.12
Геометр
Чотири точки на площині задані своїми координатами.
1. Створіть програму, яка визначає, чи можуть ці точки бути вершинами опуклого чотирикутника, і, якщо так, обчислює його периметр.
Вхідні дані
Значення x1, y1, x2, y2, x3, y3, x4, y4 (координати точок (x1; y1), (x2; y2), (x3; y3), (x4; y4)) – цілі числа з діапазону [-1000; 1000], вводяться з клавіатури.
Вихідні дані
Значення P (периметр прямокутника або, якщо задані точки не можуть бути вершинами опуклого чотирикутника, значення 0) – дійсне число, виводиться на екран.
2. Заповніть тестову таблицю за результатами роботи програми:
Номер тесту | x1 | y1 | x2 | y2 | x3 | y3 | x4 | y4 | P |
| 1 | 0 | 0 | 0 | 4 | 5 | 0 | 5 | 4 | 18.0 |
| 2 | -2 | -3 | 4 | 1 | 4 | 6 | 0 | 3 | |
| 3 | 5 | 5 | 5 | 1 | -1 | -1 | 0 | 5 | |
| 4 | 0 | 0 | 200 | 1 | 400 | 3 | -400 | 0 | |
| 5 | 0 | 0 | 5 | 5 | -5 | 5 | 0 | -5 | |
| 6 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 7 | 3 | 5 | 8 | 1 | 4 | 2 | 5 | 3 | |
| 8 | -7 | 1 | 3 | -20 | 4 | 3 | 8 | 1 | |
| 9 | 0 | 5 | 3 | 1 | 4 | -10 | 6 | 2 | |
| 10 | 0 | 0 | 200 | 2 | 400 | 3 | -400 | 0 |
Аналіз розв’язку задачі «Геометр»
Наведемо пояснення до розв’язку задачі.
Якби за умовою задачі було визначено, що координати точок вводяться в порядку обходу вершин чотирикутника, розв’язок задачі не був би складним:
• спочатку слід було б перевірити, чи є чотирикутник опуклим.
Якщо чотирикутник є опуклим, то для кожної прямої, що сполучає його суміжні вершини, решта вершин розташована по один її бік.
Для точок, що знаходяться на прямій, яка проходить через точки 1 і 2, виконується рівність:
(y-y1)*(x2-x1)-(x-x1)*(y2-y1)=0.
Для точок, розташованих по різні сторони від цієї прямої, вираз
(y-y1)*(x2-x1)-(x-x1)*(y2-y1) матиме різні знаки.
Отже, умовою розташування точок по один бік від прямої є додатність (або від’ємність) наведеного виразу. Саме це і є ключем до розв’язку задачі;
• якщо чотирикутник виявився опуклим, слід обчислити його периметр.
За умовою нашої задачі координати точок уводяться в довільному порядку, тому зазначену вище умову слід перевіряти для всіх відрізків, якими можна з’єднати задані точки. Якщо кількість відрізків, для яких умова виконується, дорівнюватиме 4, то ці відрізки і є сторонами опуклого чотирикутника, а сума їх довжин є шуканим периметром.
Тестова таблиця з результатами роботи програми:
Номер тесту | x1 | y1 | x2 | y2 | x3 | y3 | x4 | y4 | P |
| 1 | 0 | 0 | 0 | 4 | 5 | 0 | 5 | 4 | 18.0000 |
| 2 | -2 | -3 | 4 | 1 | 4 | 6 | 0 | 3 | 23.5357 |
| 3 | 5 | 5 | 5 | 1 | -1 | -1 | 0 | 5 | 21.4073 |
| 4 | 0 | 0 | 200 | 1 | 400 | 3 | -400 | 0 | 1600.0181 |
| 5 | 0 | 0 | 5 | 5 | -5 | 5 | 0 | -5 | 0 |
| 6 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
| 7 | 3 | 5 | 8 | 1 | 4 | 2 | 5 | 3 | 0 |
| 8 | -7 | 1 | 3 | -20 | 4 | 3 | 8 | 1 | 60.4989 |
| 9 | 0 | 5 | 3 | 1 | 4 | -10 | 6 | 2 | 0 |
| 10 | 0 | 0 | 200 | 2 | 400 | 3 | -400 | 0 | 0 |
Журі оцінило надіслані розв’язки наступним чином:
| № | Учасник | Кількість балів |
| 1 | Сергій Сальніков | 3 |
