Задача.
Заданы координаты вершин тругольника [latex] ABC [/latex] на плоскости. Вывести их в порядке обхода по часовой стрелке (для проверки достаточно рассмотреть знаки внутренних углов).
Задача взята из задачника по программированию Юркина.
Тесты
|
Координаты вершин [latex] x, y [/latex] [latex] a, b [/latex] [latex] c, d [/latex] |
Вывод по часовой стрелке [latex] x, y [/latex] [latex] a, b [/latex] [latex] c, d [/latex] |
| -2 -2 4 1 -1 4 | ( 4 1) (-2 -2 ) ( -1 4) |
| -2 -2 -1 4 4 1 | ( 4 1) (-2 -2 ) ( -1 4) |
| 4 1 -2 -2 -1 4 | ( 4 1) (-2 -2 ) ( -1 4) |
| 4 1 -1 4 -2 -2 | ( 4 1) (-2 -2 ) ( -1 4) |
| -1 4 -2 -2 4 1 | ( 4 1) (-2 -2 ) ( -1 4) |
| -1 4 4 1 -2 -2 | ( 4 1) (-2 -2 ) ( -1 4) |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> using namespace std; int main() { int x, y, a, b, c, d; cin >> x >> y >> a >> b >> c >> d; if ( x >= c && x >= a && c >= a && d >= b && y <= d ) { cout << " ( " << x << " " << y << " ) " << "( " << a << " " << b << " )" << " ( " << c << " " << d << " ) ";} else if ( x >= c && x >=a && a >= c && b >= d && y <= b ){ cout << " ( " << x << " " << y << " ) " << "( " << c << " " << d << " )" << " ( " << a << " " << b << " ) ";} else if ( c >= a && c >= x && x >= a && y >= b && d <= y ){ cout << " ( " << c << " " << d << " ) " << "( " << a << " " << b << " )" << " ( " << x << " " << y << " ) ";} else if ( c >= x && c >= a && a >= x && b >= y && d <= b){ cout << " ( " << c << " " << d << " ) " << "( " << x << " " << y << " )" << " ( " << a << " " << b << " ) ";} else if ( a >= c && a >= x && c >= x && d >= y && b <= d ){ cout << " ( " << a << " " << b << " ) " << "( " << x << " " << y << " )" << " ( " << c << " " << d << " ) ";} else if ( a >= c && a >= x && x >= c && y >= d && b <= y){ cout << " ( " << a << " " << b << " ) " << "( " << c << " " << d << " )" << " ( " << x << " " << y << " ) ";} return 0; } |
Решение
В задаче не указано, с какой вершины следует выводить координаты, так что за точку отсчета берется крайняя правая. Для этого находим большее из [latex] x, c, d [/latex]. Из оставшихся двух точек находим нижнюю, находя меньшее значение по оси ординат. Поскольку значения по оси ординат могут совпадать, проверяем также значение по оси абсцисс и выбираем меньшее из двух.
Так как точек три и у каждой есть два варианта расположения относительно двух других, в программе используется 6 if-ов.
Решение на ideone.
— А почему координаты целые числа? Этого в условии нет.
— Программа работает неправильно. Добавьте в тесты контрпример 2 1 0 0 2 0. Программа выдаёт ( 2 1 ) ( 0 0 ) ( 2 0 ), т.е. против часовой стрелки.