Боюсь (а вернее, точно знаю), что на объяснение того, как написать программу вывода на экран всех (!) четных чисел, потребуется весьма немало времени — или вы думаете, что это можно сделать за один урок?
Очень спорные утверждения нмв! Давайте по математике — как много людей применяет в жизни квадратные уравнения, арифметические и геометрические прогрессии, теоремы Пифагора, синусов и косинусов? По моим оптимистическим оценкам — 0.01%. Значит математику выкидываем из школьного образования? Обучаем калькулятору — этакий минимально-достаточный интерфейс к математике… Дальше русский (тут я не совсем копенгаген, если честно) — всю грамматику к черту, нас и так понимают, как слово правильно пришется — ворд подскажет, и вообще много что за нас умного сделает… Про физику, химию и биологию я вообще молчу. Что там еще осталось? С вашей точки зрения самый полезный предмет в школе — ОБЖ! А на мой взгляд, алгоритмика (реализуемая через программирование) — эта такая фундаментальная штука, которая никому не помешает, а при хорошей подаче она еще и страшно интересна. Офисные же технологии — это ведь такая тоска зеленая, а если их еще будут 6 лет в школе преподавать…
Как это определить исходя из задачи, а не просто методом тыка пальца в «узкое» место?
Вершина №4 на вашем рисунке с точки зрения теории графов называется точкой сочленения. Удаление такой вершины приводит к нарушению связности графа (он распадается на несколько несвязанных компонент, поэтому такие вершины являются критическими для разных приложений). Для поиска точек сочленения, насколько я помню, можно использовать алгоритм, основанный на обходе графа в глубину.
Нет, можно обойтись целочисленной арифметикой (при условии, что координаты являются целыми), используя функцию типа intersect, определенную выше. Главная проблема там — учет всяких граничных состояний, но тоже все решается целочисленно.
Можно и так, но это 1) опять-таки будет линейно, 2) требует применения тригонометрических функций, которые в отличие от арифметики вычисляются очень и очень долго.
Все-таки многоугольник — это ломаная линия, поэтому он обычно задается именно последовательностью точек, а не набором отрезков. Максимум плохого здесь — эта линия может быть неверно ориентирована (по часовой), но эта проблема легко решается не более чем за линейное время.
Было бы здорово, я согласен, но это требует существенно большего времени на подготовку и написание. Основной же тезис данного поста — чисто математическая задача при больших количествах параметров становится объектом теории алгоритмов.
Конечно, достоинства есть — это универсальность и простота. Ситуация примерно такая, как с поиском числа в массиве. Есть универсальный метод последовательного поиска — работает медленно (на больших массивах), но всегда, а есть двоичный поиск — работает быстро, но только на упорядоченных массивах.
Например, вы могли (бы) услышать про такой алгоритм из поста выше — цитирую: «запуск луча из заданной точки и подсчет числа его пересечений со сторонами многоугольника», там же чуть ниже объясняется основной недостаток этого алгоритма — его линейность…
ЗЫ: Кмк получаемое дерево все-таки не двоичное дерево поиска, нет?
Вершина №4 на вашем рисунке с точки зрения теории графов называется точкой сочленения. Удаление такой вершины приводит к нарушению связности графа (он распадается на несколько несвязанных компонент, поэтому такие вершины являются критическими для разных приложений). Для поиска точек сочленения, насколько я помню, можно использовать алгоритм, основанный на обходе графа в глубину.