Вам предлагается два задания с похожими условиями: задание А и задание
Условие
На плоскости дан набор точек с целочисленными координатами. Необходимо найти четырёхугольник наибольшей площади с вершинами в этих точках, две вершины которого лежат на оси Ox, а две оставшиеся - по разные стороны от оси Ox. Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Задание А. Имеется набор данных, состоящий из 10 пар координат. Напишите программу для решения такой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.Максимальная оценка за правильную программу - 2 балла. Задание Б. Имеется набор данных, состоящий из пар координат. Пар может быть много. Напишите программу для решения этой задачи.Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик).Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла.Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Описание входных данных.В первой строке вводится одно целое положительное число — количество точек N. Каждая из следующих N строк содержит два целых числа: сначала координата x, затем координата y очередной точки.Описание выходных данных.Программа должна вывести одно число — максимальную площадь четырёхгольника, удовлетворяющего условиям задачи. Если такого четырёхугольника не существует, программа должна вывести ноль. Пример входных данных:60 02 00 23 -35 -56 6Пример выходных данных для приведённого выше примера входных данных:11 Рассматривайте только четырёхугольники со сторонами лежащими не на оси Ox. Комментарий.В оригинальной формулировке задачи последнего условия нет, что создаёт дополнительные трудности при поиске необходимых четырёхугольников. Критерии оценивания выполнения задания | Баллы | Пояснения для проверяющих.1. Задание Б является усложнением задания А. Если в качестве решения задания Б представлено решение задания А, то согласно приведённым ниже критериям его оценка будет такой же, как если бы это решение было представлено в качестве решения задания А.2. Два задания (и, соответственно, возможность для экзаменуемого представить две программы) дают ученику возможность (при его желании) сначала написать менее сложное и менее эффективное решение (задание А), которое даёт ему право получить 2 балла, а затем приступить к поиску более эффективного решения.3. Приведённые в п. 2.1-2.5 правила имеют целью избежать снижения оценки из-за того, что ученик перепутал обозначения заданий | | Критерии оценивания задания А | | При решении задачи A программа верно находит требуемую суммудля любых 6 пар исходных данных. Допускается до пяти синтаксических и приравненных к ним ошибок (см. критерии оценивания задания Б на 4 балла) | 2 | Не выполнены условия, позволяющие поставить 2 балла. Из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи. Допускается любое количество «описок» | 1 | Не выполнены критерии, позволяющие поставить 1 или 2 балла | 0 | Максимальный балл для задания А | 2 | Критерии оценивания выполнения задания Б | Баллы | Программа правильно работает для любых соответствующих условию входных данных и при этом эффективна как по времени, так и по памяти, т.е. не используются массивы и другие структуры данных (в том числе стек рекурсивных вызовов), размер которых зависит от количества входных элементов, а время работы пропорционально этому количеству. Возможно использование массивов и динамических структур данных при условии, что в них в каждый момент времени хранится фиксированное количество элементов, требующих для хранения меньше 1Кб. Программа может содержать не более трёх синтаксических ошибок следующих видов:1) пропущен или неверно указан знак пунктуации;2) неверно написано или пропущено зарезервированное слово языка программирования;3) не описана или неверно описана переменная;4) применяется операция, недопустимая для соответствующего типа данных.К синтаксическим ошибкам приравнивается использование неверного типа данных. Если одна и та же ошибка встречается несколько раз, она считается за одну ошибку | 4 | Не выполнены условия, позволяющие поставить 4 балла.Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел; правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел. Количество синтаксических ошибок («описок») указанных выше видов - не более пяти.Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой структуре данных). Допускается ошибка при вводе и выводе данных, не влияющая на содержание решения.Программа может содержать не более пяти синтаксических и приравненных к ним ошибок, описанных в критериях на 4 балла.Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов:1) ошибка инициализации, в том числе отсутствие инициализации;2) не выводится результат, равный 0, или вместо 0 выводится неверное значение;3) допущен выход за границу массива;4) используется знак “<” вместо “<=”, “or” вместо “and” и т.п. | 3 | Не выполнены условия, позволяющие поставить 3 или 4 балла.Программа работает в целом верно, эффективно или нет, например для решения задачи используется перебор всех возможных вариантов выбора элементов в парах. В реализации алгоритма допускается до трёх содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла.Количество синтаксических «описок» не должно быть более семи. Программа может быть неэффективна по времени, например все числа запоминаются в массиве и перебираются все возможные суммы, т.е., по сути, реализовано решение задачи А без ограничений на количество ввёденных пар | 2 | Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может быть представлена отдельными фрагментами, без ограничений на количество синтаксических и содержательных ошибок. 1 балл ставится также за решения, верные лишь в частных случаях | 1 | Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла | 0 | Максимальный балл для задания Б | 4 | Итоговый максимальный балл | 4 |
Формат задания
Решение по шагам
Как рассуждать
Решение. Искомый четырёхугольник состоит из двух треугольников с общим основанием, лежащим на оси Ox, при этом один треугольник лежит выше этой оси, другой - ниже. Площадь четырёхугольника будет максимальной, если вершины на оси Ox будут расположены как можно дальше друг от друга, а вершины, не лежащие на этой оси, — как можно дальше от неё. Программа читает исходные данные, не запоминая все точки в массиве. Для каждой точки проверяется её принадлежность оси Ox (условие y=0). Среди точек, лежащих на оси, необходимо найти наиболее далеко отстоящие друг от друга - они дадут наибольшее возможное общее основание двух треугольников. Это будут точки с наименьшим и наибольшим значением координаты x. Среди точек, не лежащих на оси Ox, надо найти две точки, расположенные по разные стороны от оси и как можно дальше от неё, — они дадут наибольшие возможные значения высот треугольников. Это будут точки с наибольшим положительным инаименьшим отрицательным значением координаты y.Таким образом, задача сводится к нахождению максимального и минимального x среди точек, у которых y=0, максимального и минимального y среди остальных точек и нахождению площади четырёхугольника на основе этих данных.Перед выводом результата необходимо убедиться в существовании искомого четырёхугольника. Пример правильной и эффективной программы на языке Паскальprogram c4;varn: integer;x, y: integer;xmin, xmax: integer;xsearch: boolean;ymin, ymax: integer;i: integer;s: real;beginxsearch := true;xmin := 0; xmax := 0;ymin:=0; ymax := 0;readln(n);for i:=1 to n do beginreadln(x,y);if y=0 then beginif xsearch or (x < xmin) then xmin:=x;if xsearch or (x > xmax) then xmax:=x;xsearch:=false;endelse if y < ymin then ymin:=yelse if y > ymax then ymax:=yend;if (xmax>xmin) and (ymin<0) and (ymax>0)then s := (xmax-xmin)(ymax-ymin)/2else s := 0;writeln(s);end. Пример правильной и эффективной программы на языке Бейсик DIM n AS INTEGER DIM x, y AS INTEGER DIM xmin, xmax AS INTEGER DIM xsearch AS INTEGER DIM ymin, ymax AS INTEGER DIM i AS INTEGER DIM s AS DOUBLE xsearch = 1 xmin = 0: xmax = 0 ymin = 0: ymax = 0 INPUT n FOR i = 1 TO n INPUT x, y IF y = 0 THEN IF xsearch = 1 OR x < xmin THEN xmin = x IF xsearch = 1 OR x > xmax THEN xmax = x xsearch = 0 ELSEIF y < ymin THEN ymin = y ELSEIF y > ymax THEN ymax = y END IF NEXT i IF xmax > xmin AND ymin < 0 AND ymax > 0 THEN s = (xmax - xmin) * (ymax - ymin) / 2 ELSE s = 0 END IF PRINT s Пример правильной и эффективной программы на Алгоритмическом языкеалг c4начцел nцел x,yцел xmin=0, xmax=0лог xsearch=дацел ymin=0, ymax=0цел iвещ sввод nнц для i от 1 до nввод x, yесли y=0тоесли xsearch или xесли xsearch или x>xmax то xmax:=x всеxsearch:=нетиначеесли yесли y>ymax то ymax:=y всевсекцесли xmax > xmin и ymin < 0 и ymax > 0то s:=(xmax-xmin)(ymax-ymin)/2иначе s:=0всевывод sкон Пример решения задачи А на языке Паскаль. var coord: array[1..10, 1..2] of integer; {исходные данные} x, y: integer; {координаты очередной точки} xminpos, xmaxpos, yminpos, ymaxpos: integer; {координаты точек четырёхугольника с наибольшей площадью} s: real; {площадь четырёхугольника} i, j: integer;begin xminpos := MaxInt; xmaxpos := -(MaxInt-1); yminpos := MaxInt; ymaxpos := -(MaxInt-1); for i := 1 to 10 do begin read(x, y); coord[i, 1] := x; coord[i, 2] := y; end; for i := 1 to 10 do begin if (coord[i, 2] =
Осталось ещё 4 шага
Шаг 2
Шаг 3
Шаг 4
Шаг 5
Бесплатно · займёт минуту