Здравствуйте, samius, Вы писали:

S>Видимо ты хотел подставить координаты многоугольника в формулу, выражающую центр окружности?

Разумеется я этого не хотел.

S>В остальном у математики нет проблем с этой задачей.

И каково решение этой задачи? Как выглядит доказательство этого решения?

U>Математика живет с своем предельно упрощенном мире. И при этом даже в этом мире математики умеют решать лишь очень узкий набор задач. Например, на днях интересовался вопросом нахождения окружности минимального радиуса описывающей произвольный многоугольник, сложилось впечатление, что математика на этот вопрос ответить не может, хотя казалось бы задача примитивней некуда.

обычная задача с олимпиады по программированию уровня района города 10 класса

U>Так откуда у тебя берется уверенность, что подход математики, не всегда работающий даже в своем мирке, будет работать в куда более сложном реальном мире?

потому что он работает. вот только надо уметь его применять, а вот с этим умением уже труба.

DG>>критерию правильности, который ты должен был, как постановщик задачи, зафиксировать.

U>Ты конкретно можешь сказать, что нужно зафиксировать в задаче контроля расписаний? В чем смысл общими словесами сыпать, если ты даже конкретную задачу не можешь решить?

начинать с очевидного и его фиксировать.

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

также стоит зайти со стороны общей постановки.
у тебя задача — убрать шум или задача — восстановить образец?
это как раз помогает зафиксировать ответ на вопрос — точки в выходную последовательность добавляются или нет?
т.е. для последовательности a1, a3, правильный ответ: a1, a3 или a1, a2, a3.

U>Проблема в том, что после залезания под капот верхний уровень инкапсуляции начнет работать не так как раньше. Соответственно, как минимум, при понимании работы кода всегда придется держать в голове возможность того, что код ведет себя так, а не иначе из-за того, что кто-то залез под капот.

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

Здравствуйте, Undying, Вы писали:

U>Здравствуйте, samius, Вы писали:

S>>Видимо ты хотел подставить координаты многоугольника в формулу, выражающую центр окружности?

U>Разумеется я этого не хотел.

Тогда я не вижу в чем проблема

S>>В остальном у математики нет проблем с этой задачей.

U>И каково решение этой задачи? Как выглядит доказательство этого решения?
Для начала несложно показать что окружность будет одинаковая для всего множества многоугольников, чья выпуклая оболочка будет совпадать с выпуклой оболочкой заданного многоугольника.
Затем берем вершину ВО с максимально острым углом и несложным итеративным процессом выбираем еще две вершины выпуклой оболочки таким образом, что бы описывающая окружность содержала все остальные вершины выпуклой оболочки и ее радиус был минимальным.

Единственный неочевидный момент в доказательстве будет лишь тот, который будет доказывать что вершина с максимально острым углом ВО будет лежать на искомой окружности. Я думаю что это не составит проблемы.

Хотя, ВО нужна лишь для того, что бы уменьшить число итераций и зафиксировать первую вершину.
В остальном задача решается полным перебором троек вершин и доказательство решения сводится к "очевидно".

U>И при этом даже в этом мире математики умеют решать лишь очень узкий набор задач.
...
U>Именно по этой причине тесты не могут ничего гарантировать и соответственно не имеют никакого отношения к доказательству правильности кода.
..
U>Ну да, потратив кучу времени таким способом можно доказать какую-нибудь примитивную ерунду, которая и так очевидна.

всем этих утверждениях четко выражена мысль "я это делать не умею, поэтому это никто в мире делать не умеет".

зы
мантру "все остальные такие же тупые, как я" — стоит повторять по чаще.
она точно ведет к успеху

Здравствуйте, samius, Вы писали:

S>Для начала несложно показать что окружность будет одинаковая для всего множества многоугольников, чья выпуклая оболочка будет совпадать с выпуклой оболочкой заданного многоугольника.

А если многоугольник невыпуклый?

S>Затем берем вершину ВО с максимально острым углом и несложным итеративным процессом выбираем еще две вершины выпуклой оболочки таким образом, что бы описывающая окружность содержала все остальные вершины выпуклой оболочки и ее радиус был минимальным.

S>Единственный неочевидный момент в доказательстве будет лишь тот, который будет доказывать что вершина с максимально острым углом ВО будет лежать на искомой окружности. Я думаю что это не составит проблемы.

Как будет выглядеть доказательство? Сколько у тебя займет запись этого доказательства? Что гарантирует, что в процессе доказательства не было допущено ошибок?

S>Хотя, ВО нужна лишь для того, что бы уменьшить число итераций и зафиксировать первую вершину.
S>В остальном задача решается полным перебором троек вершин

Центр окружности где будет находится?

S>и доказательство решения сводится к "очевидно".

И чем это "очевидно" отличается от "мамой клянусь, что в коде нет ошибок"?

S>>Для начала несложно показать что окружность будет одинаковая для всего множества многоугольников, чья выпуклая оболочка будет совпадать с выпуклой оболочкой заданного многоугольника.

U>А если многоугольник невыпуклый?

ответ на твой вопрос уже есть в процитированном тобой утверждении samius-а

U>Как будет выглядеть доказательство? Сколько у тебя займет запись этого доказательства? Что гарантирует, что в процессе доказательства не было допущено ошибок?

доказательство (хоть и не строгое) уже приведено. то что ты его не понял — это же какая-то другая проблема, правильно?

S>>Хотя, ВО нужна лишь для того, что бы уменьшить число итераций и зафиксировать первую вершину.
S>>В остальном задача решается полным перебором троек вершин

U>Центр окружности где будет находится?

а если чуть-чуть подумать?

S>>и доказательство решения сводится к "очевидно".

U>И чем это "очевидно" отличается от "мамой клянусь, что в коде нет ошибок"?

слово "очевидно" в данном случае означает, что если чуть-чуть подумать, то все остальные выкладки "тривиальные".

Здравствуйте, Undying, Вы писали:

U>Здравствуйте, samius, Вы писали:

S>>Для начала несложно показать что окружность будет одинаковая для всего множества многоугольников, чья выпуклая оболочка будет совпадать с выпуклой оболочкой заданного многоугольника.

U>А если многоугольник невыпуклый?

Назови мне ВУЗ, который ты заканчивал. Буду рекомендовать его некоторым знакомым, которые боятся перегрузить голову.

U>Как будет выглядеть доказательство? Сколько у тебя займет запись этого доказательства? Что гарантирует, что в процессе доказательства не было допущено ошибок?

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

U>Центр окружности где будет находится?
Ответ ищи где-то в школьной геометрии.

S>>и доказательство решения сводится к "очевидно".

U>И чем это "очевидно" отличается от "мамой клянусь, что в коде нет ошибок"?
Вообще говоря, правильность подхода не гарантирует отсутствие ошибок в коде, как и наоборот, отсутствие ошибок в коде не гарантирует корректность выбранного метода решения задачи.

Здравствуйте, DarkGray, Вы писали:

U>>Центр окружности где будет находится?
DG>а если чуть-чуть подумать?

Давай конкрентно — явки, пароли. Что за дурацкая манера не отвечать на прямо поставленный вопрос?

S>>В остальном задача решается полным перебором троек вершин
U>>Центр окружности где будет находится?
DG>а если чуть-чуть подумать?

U> Давай конкрентно — явки, пароли. Что за дурацкая манера не отвечать на прямо поставленный вопрос?

центр окружности будет находится в центре окружности, проходящей через три данные вершины

Здравствуйте, DarkGray, Вы писали:

U>> Давай конкрентно — явки, пароли. Что за дурацкая манера не отвечать на прямо поставленный вопрос?
DG>центр окружности будет находится в центре окружности, проходящей через три данные вершины

Правда? И для вытянутого ромба тоже? Через какие такие три вершины будет проходить центр минимальной описывающей окружности в этом случае?

Здравствуйте, samius, Вы писали:

S>Назови мне ВУЗ, который ты заканчивал. Буду рекомендовать его некоторым знакомым, которые боятся перегрузить голову.

Тебя, как и Darkgray'я, тоже в элитном вузе учили, что окружность минимального радиуса описывающая многоугольник должна проходить не менее чем через три точки?

Здравствуйте, Undying, Вы писали:

U>Здравствуйте, samius, Вы писали:

S>>Назови мне ВУЗ, который ты заканчивал. Буду рекомендовать его некоторым знакомым, которые боятся перегрузить голову.

U>Тебя, как и Darkgray'я, тоже в элитном вузе учили, что окружность минимального радиуса описывающая многоугольник должна проходить не менее чем через три точки?

Меня этому не учили, но для меня это очевидно.

Здравствуйте, samius, Вы писали:

S>Меня этому не учили, но для меня это очевидно.

Для вытянутого ромба центр окружности минимального радиуса будет лежать на середине отрезка соединяющего две наиболее удаленные друг от друга вершины, и на этой окружности будет лежать всего две вершины. Если ты этого не смог понять даже с подсказкой, то мне страшно подумать чему учат в элитных вузах, похоже догматизму и апломбу.

Здравствуйте, Undying, Вы писали:

U>Здравствуйте, samius, Вы писали:

S>>Меня этому не учили, но для меня это очевидно.

U>Для вытянутого ромба центр окружности минимального радиуса будет лежать на середине отрезка соединяющего две наиболее удаленные друг от друга вершины, и на этой окружности будет лежать всего две вершины. Если ты этого не смог понять даже с подсказкой, то мне страшно подумать чему учат в элитных вузах, похоже догматизму и апломбу.

Да, поймал. Однако этот аспект не придает задаче принципиально иную сложность.
В свою очередь выражаю недоумение по поводу "вытянутого ромба". Что такое ромб — знаю.

U>Правда? И для вытянутого ромба тоже? Через какие такие три вершины будет проходить центр минимальной описывающей окружности в этом случае?

через две реальных и одну виртуальную

согласен. есть такой вырожденный случай. для него центр окружности будет в центре самой отдаленной пары вершин.

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

Здравствуйте, DarkGray, Вы писали:

DG>согласен. есть такой вырожденный случай. для него центр окружности будет в центре самой отдаленной пары вершин.

Для космических кораблей ты также собрался алгоритмы доказывать? Этот алгоритм работает правильно, т.к. его доказательство очевидно? А когда космический корабль упадет будешь говорить, что ничего страшного, зато узнали, что у доказательства был вырожденный случай?

DG>зы
DG>этим бывает хороши строгие доказательства, там явно всплывают все вырожденные случаи.

И где строгое доказательство для данной задачи?

Здравствуйте, Undying, Вы писали:

U>И где строгое доказательство для данной задачи?

Как для выпуклого многоугольника построить описывающую окружность очевидно?

U>Для космических кораблей ты также собрался алгоритмы доказывать? Этот алгоритм работает правильно, т.к. его доказательство очевидно? А когда космический корабль упадет будешь говорить, что ничего страшного, зато узнали, что у доказательства был вырожденный случай?

да, в конечном счете все упирается в человеческий фактор.
но у доказательства есть весомое преимущество: доказательный метод позволяет перейти от проверки(доказательства) целой большой сложной штуковины к проверке(доказательству) последовательности небольших локальных выводов (каждый из которых либо верен, и тогда верно всё, либо не верен — и тогда не верно всё).
и соответственно с доказательным методом намного проще добиться еще одной девятки надежности (а потом еще одной и т.д.) — достаточно цепочку выводов показать еще одну человеку (и еще одному и т.д.), который перепроверить каждый вывод — и вынесет вердикт: какие шаги верны, какие — нет, какие сомнительные, какие — неточные и т.д.

U>И где строгое доказательство для данной задачи?

для строгого доказательства необходимо доказать, что ответ — является решением (все точки в него входят), и при этом ответ — является минимальным решением (меньше построить нельзя)

базовое утверждение 1 — окружность задается не больше, чем тремя точками (это есть следствие того, что через любые три точки можно провести _единственную_ окружность), остальные точки тоже могут лежат на окружности, но они не требуются для ее задания.
назовем такие точки опорными.

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

диаметр описанной окружности равен длине стороны поделенной на синус противоположного угла (D = a / sin A)

для первого случая (остроугольный) — если окружность не касается одной из вершин, то можно построить треугольник со следующими вершинами (две оставшиеся + одна на окружности) причем такой, что исходный треугольник лежит внутри него.
у исходного треугольника и у данного треугольника — опорная сторона общая при этом у нового треугольника угол более острый, и на основе формулы диаметра и того, что sin a1 < sin a2 (при 0 < a1 < a2 < 90), получаем что у нового треугольника диаметр окружности больше.
для второго случая — меньше диаметра расстояний в окружности не бывает, поэтому построить окружность меньшего размера нельзя.
при этом тупая вершина входит в окружность построенной на большей стороне.


доказательство:
возьмем бесконечную окружность вокруг многоугольника и начнет ее стягивать вокруг многоугольника.
она будет стягиваться пока не упрется в вершины многоугольника
таких вершин может быть от 2 до всех вершин многоугольника, но из базового утверждения следует, что опорных вершин будет не больше 3.
переберем все такие множества (из 2 и 3 точек) и выберем из него такое, которое образует окружность с минимальным радиусом, в которые входят все остальные точки.

ответ является искомым потому что все точки в него входят,
меньше быть не может следует из базового утверждения 2