Задача 20.
На квадратном торте N свечей. Можно ли одним прямолинейным разрезом разделить его на две равные по площади части, одна из которых не содержала бы ни одной свечи? Свечи будем считать точками, у которых известны их целочисленные координаты Х[1], Y[1]; ...; Х[N], Y[N] (начало координат - в центре торта); разрез не может проходить через свечу.
|
Решение задачи 20.
Понятно, что если есть свеча с нулевыми координатами или две свечи лежат на прямой, проходящей через начало координат, по разные стороны от начала координат, то решения не существует. Пусть таких свеч нет.
Проведем линию через центр и первую свечу (пусть это точка А). Если все свечи оказались по одну сторону линии, то решение построено. Предположим, что существуют свечи по разные стороны прямой. Определим направление прямой от центра к свече, и пусть М - множество точек, лежащих по правую сторону от прямой. Определим среди них точку В, для которой угол АОВ максимальный и лежит в пределах от 0 до 180 градусов. Это можно определить через косинус угла АОВ ( большему углу соответствует меньший косинус). Проведя вторую линию ОВ, проверяем, лежат ли все свечи по одну сторону от нее. Если да, то решение найдено. Если нет, то решения нет.
|
