СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 27 № 6906

На плос­ко­сти дан набор точек с це­ло­чис­лен­ны­ми ко­ор­ди­на­та­ми. Не­об­хо­ди­мо найти четырёхуголь­ник наи­боль­шей пло­ща­ди с вер­ши­на­ми в этих точ­ках, две вер­ши­ны ко­то­ро­го лежат на оси Ox, а две остав­ши­е­ся – по раз­ные сто­ро­ны от оси Ox.

 

Вам пред­ла­га­ет­ся два за­да­ния с по­хо­жи­ми усло­ви­я­ми: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. За­да­ние Б более слож­ное, его ре­ше­ние оце­ни­ва­ет­ся выше. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б.

 

За­да­ние А. Име­ет­ся набор дан­ных, со­сто­я­щий из 10 пар ко­ор­ди­нат.

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

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му – 2 балла.

 

За­да­ние Б. Име­ет­ся набор дан­ных, со­сто­я­щий из пар ко­ор­ди­нат. Пар может быть много.

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

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству пар чисел N, т. е. при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз.

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если раз­мер па­мя­ти, ис­поль­зо­ван­ной в про­грам­ме для хра­не­ния дан­ных, не за­ви­сит от числа N и не пре­вы­ша­ет 1 ки­ло­бай­та.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и па­мя­ти, — 4 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти, — 3 балла.

 

Перед тек­стом про­грам­мы крат­ко опи­ши­те ал­го­ритм ре­ше­ния за­да­чи и ука­жи­те ис­поль­зу­е­мый язык про­грам­ми­ро­ва­ния и его вер­сию. Опи­са­ние вход­ных дан­ных.

В пер­вой стро­ке вво­дит­ся одно целое по­ло­жи­тель­ное число — ко­ли­че­ство точек N. Каж­дая из сле­ду­ю­щих N строк со­дер­жит два целых числа: сна­ча­ла ко­ор­ди­на­та x, затем ко­ор­ди­на­та y оче­ред­ной точки.

Опи­са­ние вы­ход­ных дан­ных.

Про­грам­ма долж­на вы­ве­сти одно число — мак­си­маль­ную пло­щадь четырёхголь­ни­ка, удо­вле­тво­ря­ю­ще­го усло­ви­ям за­да­чи. Если та­ко­го четырёхуголь­ни­ка не су­ще­ству­ет, про­грам­ма долж­на вы­ве­сти ноль.

При­мер вход­ных дан­ных:

6

0 0

2 0

0 2

3 -3

5 -5

6 6

При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных:

11

 

Рас­смат­ри­вай­те толь­ко четырёхуголь­ни­ки со сто­ро­на­ми ле­жа­щи­ми не на оси Ox.

 

Ком­мен­та­рий.

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

Решение.

Искомый четырёхугольник состоит из двух треугольников с общим основанием, лежащим на оси Ox, при этом один треугольник лежит выше этой оси, другой – ниже. Площадь четырёхугольника будет максимальной, если вершины на оси Ox будут расположены как можно дальше друг от друга, а вершины, не лежащие на этой оси, — как можно дальше от неё. Программа читает исходные данные, не запоминая все точки в массиве. Для каждой точки проверяется её принадлежность оси Ox (условие y=0). Среди точек, лежащих на оси, необходимо найти наиболее далеко отстоящие друг от друга – они дадут наибольшее возможное общее основание двух треугольников. Это будут точки с наименьшим и наибольшим значением координаты x. Среди точек, не лежащих на оси Ox, надо найти две точки, расположенные по разные стороны от оси и как можно дальше от неё, — они дадут наибольшие возможные значения высот треугольников. Это будут точки с наибольшим положительным и

наименьшим отрицательным значением координаты y.

Таким образом, задача сводится к нахождению максимального и минимального x среди точек, у которых y=0, максимального и минимального y среди остальных точек и нахождению площади четырёхугольника на основе этих данных.

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

 

Пример правильной и эффективной программы на языке Паскаль

program c4;

var

n: integer;

x, y: integer;

xmin, xmax: integer;

xsearch: boolean;

ymin, ymax: integer;

i: integer;

s: real;

begin

xsearch := true;

xmin := 0; xmax := 0;

ymin:=0; ymax := 0;

readln(n);

for i:=1 to n do begin

readln(x,y);

if y=0 then begin

if xsearch or (x < xmin) then xmin:=x;

if xsearch or (x > xmax) then xmax:=x;

xsearch:=false;

end

else if y < ymin then ymin:=y

else if y > ymax then ymax:=y

end;

if (xmax>xmin) and (ymin<0) and (ymax>0)

then s := (xmax-xmin)*(ymax-ymin)/2

else 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] = 0) and (coord[i, 1] < xminpos) then xminpos := coord[i, 1];

if (coord[i, 2] = 0) and (coord[i, 1] > xmaxpos) then xmaxpos := coord[i, 1];

if (coord[i, 2] <> 0) and (coord[i, 2] < yminpos) then yminpos := coord[i, 2];

if (coord[i, 2] <> 0) and (coord[i, 2] > ymaxpos) then ymaxpos := coord[i, 2];

end;

if (xminpos = xmaxpos) or (yminpos = ymaxpos) or (xminpos = MaxInt) then

s := 0

else s := (xmaxpos - xminpos)*(ymaxpos-yminpos)/2;

writeln(s);

end.