Bednistudent
Newbie | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору Пожалуйста помогите с задачей. Нужно написать програму на Паскале,а у меня неполучается(( Вот задача "Деревья моего острова" Я купил остров,на котором хочу посадить деревья рядами и столбцами.Деревья будут формировать прямоугольную сетку,так что можно считать,что каждое из них имеет целочисленые координаты,если выбрать подходящую точку сетки в качестве начала координат. Но мой остров не прямоугольный.Я нашёл простую многоугольную область внутри острова с вершинами,лежащими в узлах сетки,и решил,что деревья будут высаживатся только в узлах сетки находящихся внутри многоугольника. Мне нужна ваша помощ ,чтобы подсчитать,сколько деревьев я могу посадить. Входные данные: Входной файл может содержать несколько тестовых блоков.Каждый тестовый блок начинается со строки,содержащей целое число N(3<=N<=1000) задающее число вершин многоугольника.Следующие N строк содержат вершины многоугольника,перечисляемые по или против часовой стрелки.Каждая из этих N строк содержит два целых числа,задающих x-и y-координаты вершины.Абсолютное значение ни одной из координат не превышает 1000000. Тестовый блок,содержащий в первой строке 0 в качестве N ,завершает входные данные. Выходные данные: Для каждого тестового блока выведите строку,содержащую число деревьев,помещающихся внутри многоугольника. Также мне предложили алгоритм решения. Вот он: 1. Перебираем последовательно все узлы нашей прямоугольной координатной сетки. Координаты X,У от 0 до К. 2, Из каждой точки координатной сетки строим луч. Например в право. Т.е. координата У остается неизменной, координата X меняется в положительную сторону. Идея в том, что если точка нашей прямоугольной координатной сетки находится внутри многоугольника, то проведенный из нее луч будет иметь не четное количество пересечений сторон многоугольника. Если таких пересечений нет, либо их четное количество, то точка на нашей прямоугольной координатной сетке находится за пределами многоугольника. Если рассматривать вырожденный случай - выпуклый многоугольник, то пересечений может быть либо одно => точка находится внутри выпуклого многоугольника, либо 2 точка слева(за пределами) от выпуклого многоугольника и луч пронзает его насквозь, либо 0 - точка находится справа от многоугольника. 3) Для реализации алгоритма берем последовательно каждую точку нашей прямоугольно сетки, фиксируем значение У, затем берем из входных данных пары координат вершин многоугольника. 1-ю и 2-ю, 2-ю и 3-ю, 3-ю и 4-ю,...N-ю и 1-ю. И смотрим не пересекает ли луч проведенный из точки грань многоугольника образованную парой вершин. А именно, если (координата У1 1-ой точки вершины многоугольника >= координаты У, а координата 2-ой вершины многоугольника У2<= координаты У) или (координата У1 1-ой точки вершины многоугольника <= координаты У, а координата 2-ой вершины многоугольника У2>= координаты У) , то считаем что грань пересечена лучом, если нет, то не пересекалась. Если У1=У2, то следующую пару вершин пропускаем. Так перебираем все пары вершин. Каждый раз при нахождении пересечений увеличиваем соответствующий счетчик. 4) После завершения перебора всех пар вершин проверяем счетчик пересечений если он имеет не четное значение, то точка находится внутри многоугольника => счетчик количества деревьев увеличиваем на одно, если счетчик пересечений имеет четное значение либо 0 => счетчик количества деревьев остается неизменным. 5) Переходим к следующей точке нашей прямоугольной координатной сетки. 6) Если координаты этой точки < предельных координат сетки (К.К) переходим к пункту 2, если превышают (К,К), то подсчитываем и выводим значение счетчика количества деревьев. Но у меня неполучается написать по нему програму на Pascal.(( Пожалуйста помогите.Одна надежда на вас. |