Условие
На плоскости дано
N точек, никакие три из которых не лежат на одной прямой. Если
A,
B,
C — любые три из них, то внутри
треугольника
ABC нет ни одной точки из данных. Доказать, что эти точки можно
занумеровать так, что многоугольник
A1A2...
An будет выпуклым.
Решение
Рассмотрим выпуклую оболочку всех точек — это выпуклый многоугольник
M с
вершинами в данных точках. Докажем, что ни одна из точек не может лежать на
стороне и внутри многоугольника. Для этого рассмотрим одну из вершин, тогда
весь многоугольник разбивается диагоналями, проведёнными из данной вершины, на
треугольники, причём ни в одном из них по условию не может лежать ещё одна из
данных точек. Значит, все данные точки являются вершинами многоугольника
M,
т. е.
M является искомым выпуклым многоугольником.
Источники и прецеденты использования
