Задача о выпуклом N-угольнике

62408

Пожалуйста, помогите решить задачу:
Дан выпуклый N-угольник, где N<100, и мн-во A = {A_1, ..., A_100} некоторых точек этого многоугольника. Известно, что все N вершин N-угольника принадлежат мн-ву A, и что никакие 3 точки не лежат на одной прямой, а никакие 4 точки не лежат на двух параллельных прямых. Разрешается задавать вопросы типа: чему равна площадь треугольника A_iB_jC_k? Докажите, что 300 вопросов достаточно, чтобы выяснить, какие точки являются вершинами многоугольника, и чтобы найти площадь многоугольника.

griz_a

Если дан многоугольник, то вообще ничего не надо спрашивать. Как вообще точки многоугольника отделяются от других точек множества этими вопросами по-твоему?

62408

Те точки, что даны - точки многоугольника, одни - вершины, другие - внутренние.
Других нет.

griz_a

Ты можешь спрашивать площадь треугольника в вершинах с данными точками? Тогда в чем смысл вопроса? И разве он отделяет как-то точки многоугольника от точек множества?

62408

Почитай внимательно задачу.
И разве он отделяет как-то точки многоугольника от точек множества?

Что в твоём понимании "множество"?
В понимании авторов задачи (и моём) множество А состоит из точек, которые принадлежат многоугольнику. Всего точек 100, N из них - вершины.
Никакого другого множества нет.
Поэтому твой вопрос выше бессмысленный.

griz_a

Итак. Есть 100 точек, но мы не знаем, какие из них точки многоугольника? Тогда очевидно - берем выпуклую оболочку, вот и всё. Или нам они не даны? Тогда мы их не найдем, очевидно. Если задача просто найти площадь многоугольника, то условие ясно. В той форме, в какой ты пишешь - нет

griz_a

Есть гипотеза, что точки все-таки не даны, а под "найти точки, являющиеся вершинами" ты подразумеваешь "узнать их номера". Тогда условие понятно.

62408

Это не я подразумеваю. Это - авторы задачи подразумевают. Никаких дополнительных данных о многоугольнике нет. Только есть информация о площади треугольников.

62408

Если интересно, это задача из книжки В.И.Кудрявцева, Э.Э. Гасанова , А.С. Подколзина "Введение в теорию интеллектуальных систем"

a101



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

a101



Но вот как это сделать за 300 - буду думать.
292 достаточно Можно даже перечислить его точки на границе в порядке обхода
PS
Решение писать?

62408

Можешь написать мне в приват
А Фрау Соболева пусть пока разбирается с множествами
292 - логично (первый треугольник - 1 + 97*3 (291 вариант) = 292)
А вот о каких трёх треугольниках спрашивать на каждом шаге при добавлении след. точки - вопрос
Оставить комментарий
Имя или ник:
Комментарий: