Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Задача геометрическая

Автор: Ozzя 13.01.2007 12:40

Цитата

Определить, имеют ли общие точки две плоские фигуры – треугольник с заданными координатами его вершин и круг радиусом R c центром в начале координат.

Что-то вовсе туплю

Не соображу, как подступиться
Пните, пожалуйста, в правильном направлении.

Автор: Michael_Rybak 13.01.2007 14:15

Пусть вершины треугольника - точки А, В и С.

1. Проверяешь, лежит ли точка А в круге. Проверяешь, лежит ли точка (0, 0) в треугольнике.
2. Если нет, то мы исключили вариант, когда круг полностью лежит в треугольнике, или наоборот. Теперь, если общие точки есть, то общие точки должны быть и у контуров фигур. Значит, нужно написать функцию, которая будет проверять наличие пересечения между отрезком (стороной) и окружностью, и вызвать ее для каждой стороны.
3. Отрезок пересекает окружность, если а) один конец - внутри, другой снаружи, либо 2) оба конца - снаружи, а основание перпендикуляра, опущенного из центра окружности на прямую, содержащую отрезок, лежит внутри круга, и принадлежит отрезку.

Автор: Archon 14.01.2007 4:30

Цитата

1. Проверяешь, лежит ли точка А в круге. Проверяешь, лежит ли точка (0, 0) в треугольнике.

Этими проверками не корректно исключать

Цитата

вариант, когда круг полностью лежит в треугольнике, или наоборот

Ты легко можешь исключить варианты, когда пересечения присутствуют.

Автор: мисс_граффити 14.01.2007 4:36

Так если одна из фигур лежит внутри другой, общие точки тоже есть.
Все правильно...

Автор: Archon 14.01.2007 4:51

Но как этими проверками определить, лежит ли одна фигура внутри другой?

Автор: мисс_граффити 14.01.2007 4:56

нам не надо это определять однозначно! главное, что если одна фигура лежит внутри другой, п.1 гарантированно выполняется. согласен?
а что вместе с этим идут "лишние" варианты - не страшно, т.к. они тоже удовлетворяют условию задачи.

Автор: Archon 14.01.2007 5:14

Хорошо... Проверяя пункт 1, мы делим все возможные варианты на те, в которых возможно, что одна фигура лежит внутри другой, и те, в которых это не возможно. Что это даёт?

Автор: мисс_граффити 14.01.2007 5:18

проверяя первый пункт, мы выделяем группу случаев, удовлетворяющих двум условиям:
1) фигуры однозначно имеют общие точки
2) если одна фигура лежит внутри другой, то этот случай однозначно войдет в группу.

после этого мы можем сказать, что, если первое условие не выполнено, но фигуры имеют общие точки, то и их стороны имеют общие точки.

Автор: Bokul 14.01.2007 5:19

Цитата

Проверяя пункт 1, мы делим все возможные варианты на те, в которых возможно, что одна фигура лежит внутри другой, и те, в которых это не возможно. Что это даёт?

Исключаем два первых варианты:

Автор: Archon 14.01.2007 5:26

Чёрт! Не понял условие... Там ведь круг, а не окружность. И треугольник очевидно заполненный. Извиняюсь за лишнюю панику