Югорский НИИ информационных технологий

Югорский государственный университет

Институт развития образования ХМАО-Югры

Телекоммуникационный проект "Задача в неделю"

Занятие № S (04 мая 2009 года)

Задания проекта в этом учебном году выбираются на сайте <Олимпиады по информатике (ХМАО-Югра)>. Для работы с этим ресурсом надо на нём зарегистрироваться. После этого вы сможете не только сдавать задания нашего проекта, но и самостоятельно решать задачи из <Архива задач> и принимать участие в соревнованиях (раздел <Олимпиады>). На выполнение сегодняшнего задания отводится одна неделя - до 10 часов московского времени 11 мая.

530. Черно-белая графика

(Время: 1 сек. Память: 16 Мб)

Одна из базовых задач компьютерной графики - обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной w и высотой h, разбитых на w×h единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

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

Например, для операции <исключающее ИЛИ> эта таблица выглядит так:

Требуется написать программу, которая вычислит результат попиксельного применения заданной логической операции к двум черно-белым изображениям одинакового размера.

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

Первая строка входного файла INPUT.TXT содержит два целых числа w и h (1 ≤ w, h ≤ 100). Последующие h строк описывают первое изображение и каждая из этих строк содержит w символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка входного файла содержит описание логической операции в виде четырех чисел, каждое из которых - ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента - нули, второе - результат в случае, если первый аргумент - ноль, второй - единица, третье - результат в случае, если первый аргумент - единица, второй - ноль, а четвертый - в случае, если оба аргумента - единицы.

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

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

Пример

533. Треугольники

(Время: 2 сек. Память: 16 Мб Баллы: 100)

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

Напомним, что треугольник называется равнобедренным, если его площадь положительна, и у него есть хотя бы две равные стороны.

Недавно Петя, зайдя в класс, увидел, что на доске нарисовано n точек. Разумеется, он сразу задумался, сколько существует троек из этих точек, которые являются вершинами равнобедренных треугольников.

Требуется написать программу, решающую указанную задачу.

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

Входной файл INPUT.TXT содержит целое число N (3 ≤ N ≤ 1500). Каждая из последующих строк содержит по два целых числа - x_i и y_i - координаты i-ой точки. Координаты точек не превосходят 10⁹ по абсолютной величине. Среди заданных точек нет совпадающих.

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

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

Сдать решения этой задачи можно в разделе <Олимпиады> в указанное там время. Для этого выберите олимпиаду <Занятие S проекта> и подайте заявку на участие в ней. После сдачи задачи прошу прислать на мой электронный адрес описание результатов вашей работы (оформляйте это одним файлом, содержащим ваши персональные данные, описание алгоритма и текст вашей программы).

На основе результатов сдачи и присланных материалов будет подготовлен разбор задачи.

Успехов!

Ведущий проекта, к.п.н., доцент

Алексеев Александр Владимирович,

e-mail - aav@uriit.ru, internet - http://zvn.uriit.ru/.