Задача 33.
Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел (x1,y1), ..., (xk,yk). Первая и последняя вершины лежат на границе круга, а остальные внутри его. Определить, можно ли разъединить две получившиеся части круга (выход из плоскости и повороты разнимаемых частей не допускается).
|
Решение задачи 33.
Будем обозначать через Vi вершину ломаной с координатами (xi,yi).
Сначала рассмотрим разрез круга ломаной, состоящей только из двух ребер R1=(V1,V2) и R2=(V2,V3). Для того, чтобы разнять этот круг, необходимо тянуть в направлении вектора S, выходящего из точки V2 и лежащего либо внутри угла V1 V2 V3 (вершина угла -- точка V2), либо внутри центральносимметричного ему относительно точки V2 угла. Будем говорить, что вектор S лежит в конусе C2 с вершиной V2.
Аналогично, если ломаная определяется k вершинами, то для каждой пары ребер (Vi,Vi+1) и (Vi+1,Vi+2), i=1, ..., k-2, определяем конус Ci+1 возможных направлений перемещения, затем считаем, что параллельным переносом вершины всех конусов совмещены в одной точке. Пересечение всех Ci, i=2,...,k-1, и даст искомое возможное направление разнимания круга. Если это пересечение пусто, то круг разнять нельзя, иначе - можно.
|
