Фирма, в которой работает ваш друг, недавно провела рекламную акцию «Сфотографируй маршрутку — получи приз», в рамках которой пассажиры могли присылать свои фотографии маршруток этой фирмы, а потом специальная конкурсная комиссия выбирала из них лучшие и награждала победителей. Теперь организаторы собираются выставить все фотографии на сайт фирмы.

При подготовке фотографий возникла одна проблема: видимо, некоторые пассажиры фотографировали маршрутки наспех, и потому некоторые фотографии оказались перекошенными: те линии, которые по идее должны быть горизонтальными, оказались наклонными (см. рис.). Администратор сайта категорически отказался выставлять такие фотографии на сайт, порекомендовав организаторам повернуть и обрезать фотографии так, чтобы горизонтальные линии стали на самом деле горизонтальными.

Поэтому организаторы провели большую работу и для каждой фотографии определили, под каким углом на фотографии наклонён горизонт. Теперь им надо вырезать из фотографии прямоугольник, у которого две стороны были бы параллельны горизонту, а две другие, конечно, перпендикулярны. Организаторы хотели вырезать прямоугольник наибольшей возможной площади, удовлетворяющий этому условию, но администратор сайта упростил им работу, потребовав сохранить отношение сторон фотографии. Таким образом, им теперь надо из каждой фотографии вырезать прямоугольный кусок со сторонами, параллельными и перпендикулярными горизонту, и с тем же отношением сторон, что и у оригинальной фотографии, причём среди всех таких прямоугольников выбрав наибольший по площади.

Зная вашего друга не только как хорошего экономиста, но и человека со связями, они обратились к нему с просьбой найти программу, которая помогла бы им выбрать нужный прямоугольник. Ваш друг перенаправил эту просьбу к вам.

Обратите внимание, что порядок сторон администратору сайта важен: если на оригинальной фотографии ширина была w, а высота h, а у найденного прямоугольника ширина (т. е. сторона, параллельная горизонту)w , а высота (т. е. вторая сторона) h, то должно быть , а не .

В плоской стране все было как в настоящей, только плоское, и люди и горы и все, все, все. Жили в этой стране люди хорошие, но иногда попадались преступники и тогда их отвозили на плоский остров и там оставляли поразмыслить о жизни. А чтобы они не сбежали с острова, было решено построить наблюдательную вышку, с которой можно было бы следить за преступниками. Но, так как жители страны были плоскими, то и мозги у них были тоже плоскими и никак они не могли определить, в каком месте построить вышку и какой высоты. Помогите им. Вам предлагается найти самую низкую точку — координаты верхней точки вышки (плоские люди были экономными), из которой видно крайние точки острова, и найти высоту вышки. Как выяснили плоские ученые, профиль острова позволял построить вышку высотой не более 20000 метров. Профиль острова — это ломаная, имеющая примерно такой же вид как на рисунке. На острове нет лагун и с каждой вершины видны оба склона этой вершины. Точки С и Д — это крайние точки острова.

«И молвил тогда Король: Ты храбро сражался, Рыцарь, и твой подвиг не будет забыт в веках. За доблесть твою я дарую тебе сей замок и земли вокруг него. Однако нарушен был тобой строжайший из запретов все войны видели, как ты сражался без Шляпы на голове подобно дикарям, и их злые духи могли вселиться в тебя. Ты знаешь, что закон предков велит отправлять на небеса души подобных тебе, пока зло, которое могло укорениться в них, не вырвалось наружу. Но в моей воле пощадить тебя, ибо я вижу, что ты достаточно силен чтобы не позволить этому злу проникнуть в мысли и душу твои. Ты должен дать обет три месяца и три дня не покидать своей земли и каждый день три часа после захода солнца молить добрых духов о защите. Дела торопят меня, и не могу я препроводить тебя до замка. Поэтому я дарую тебе и дорогу от этого места до замка. А сейчас иди, и возвращайся по истечении срока.»

— так записано в Зеленой Книге Лет.

Помимо этого из Зеленой Книги Лет известно, что земли, вместе с которыми был дарован замок, имели форму круга. Король был очень мудр и, во избежание лишних разбирательств относительно права на землю всегда даровал только области земли, на карте имеющие выпуклую форму. Недавно в распоряжении историков оказалась информация о том, где располагался замок и где происходил этот исторический разговор. Их интересует, участок земли какой площади получил Рыцарь в предположении, что дорога до замка была идеально прямой.

Империя обнаружила мятежников на ледяной планете Хот! По сведениям разведки все командование Альянса Повстанцев сейчас скрывается на базе «Эхо», спрятанной в горах на севере этой суровой планеты.

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

Перед тем как начинать операцию по уничтожению повстанцев, требуется лишить их базу силового поля, уничтожив эти N станций точечным бомбометанием. Однако точные координаты этих станций нам неизвестны. Ваша цель — узнать расположение станций-ретрансляторов, чтобы наши войска смогли начать наступление.

На планете введена система координат, устроенная таким образом, что все станции-ре-транс-ля-торы находятся в точках с целыми координатами, не превосходящими C по модулю.

В вашем распоряжении есть зонд-разведчик, оснащенный специальным оборудованием, позволяющим регистрировать станции-ретрансляторы. Если запустить его по прямой над базой повстанцев, по его информации можно будет узнать, сколько станций-ретрансляторов располагаются слева, и сколько — справа от прямой его движения. Станции, находящиеся на его пути, зонд не регистрирует.

С повстанцами надо расправиться как можно скорее: у вас есть время не более чем на 10⁵ запусков этого зонда. Восстановите по полученной от него информации точные координаты станций-ретрансляторов, чтобы мы могли начать наступление, и Империя вас не забудет!

В городе, являющемся одним из ведущих Российских образовательных центров, решили построить пивную. Естественно, что ректоры находящихся в городе ВУЗов потребовали, чтобы пивная была максимально удалена от каждого из ВУЗов. Помогите директору будущей пивной выбрать оптимальное место для строительства. Граница города представляет собой выпуклый многоугольник. Положение ВУЗов задается координатами точек внутри этого многоугольника. Пивную нужно построить так, чтобы расстояние от нее до ближайшего вуза было максимально. Пивную можно строить как внутри города, так и на его границе.