ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102932
Тема:    [ Площадь ]
Сложность: 3
Классы:
Название задачи: Торт для Жюри .
В корзину
Прислать комментарий

Условие

K членов Жюри Десятой Всероссийской олимпиады школьников по информатике решили отметить столь круглую годовщину в одном из лучших ресторанов на Невском проспекте. На десерт вниманию Жюри предложили торт, имеющий форму прямоугольной призмы с выпуклым N-угольником в основании. Жюри вооружается десертными ножами и собирается справедливо разделить торт на K частей равного объема. Ножами можно проводить прямые вертикальные разрезы от одной границы торта до другой; различные разрезы могут иметь общие точки лишь в своих концевых вершинах.

Напишите программу, помогающую членам Жюри построить требуемые K-1 разрезов.

Входные данные

В первой строке входного файла содержатся два целых числа K и N (1 ≤ K, N ≤ 50). Далее следуют N пар вещественных чисел – координаты
последовательно расположенных вершин N-угольника.

Выходные данные

Каждый из K-1 разрезов в выходном файле должен быть представлен четверкой чисел – координатами своих концов. Все числа должны быть разделены пробелами и/или символами перевода строки.

Пример входного файла

4 3
2 1
0 0.5
4 0.5

Пример выходного файла

2 1 1 0.5
2 1 2 0.5
2 1 3 0.5

Решение

Скачать архив тестов и решений

Найдем площадь основания куска торта для одного члена Жюри. Для этого вычислим общую площадь многоугольника S и разделим ее на количество членов K. Отрезать куски членов Жюри будем по очереди: сначала отрежем первому, затем от оставшегося многоугольника отрежем второму и т.д. Все разрезы при этом будем проводить через первую вершину исходного многоугольника. 

Для отрезания очередного куска поступим так. Один конец разреза уже фиксирован, а второй перемещается по контуру оставшегося многоугольника до тех пор, пока не «отмерит» нужную площадь. Сначала он перемещается, прыгая от одной вершины многоугольника к следующей (каждый раз при этом к площади ранее отмеренного куска добавляется площадь треугольника, образованного первой, текущей и следующей вершинами). Как только мы отмерим лишнего (т.е. площадь куска, отрезанного через текущую вершину, меньше S / K, а через следующую – больше), в качестве второго конца разреза нужно взять точку на только что пройденной стороне многоугольника. Осталось разделить эту сторону в отношении, приводящем к куску требуемой площади. 

Упражнение

Решите аналогичную задачу о разрезании для случая невыпуклого торта и K = 2, 3.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 4
Название Вычислительная геометрия
Задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .