Отправлено: 02.04.14 10:21. Заголовок: Задача с http://inf.reshuege.ru

C 4 № 6906.

цитата:

На плоскости дан набор точек с целочисленными координатами. Необходимо найти четырёхугольник наибольшей площади с вершинами в этих точках, две вершины которого лежат на оси Oy, а две оставшиеся — по разные стороны от оси Oy. Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Описание входных данных. В первой строке вводится одно целое положительное число — количество точек N. Каждая из следующих N строк содержит два целых числа: сначала координата x, затем координата y очередной точки. Описание выходных данных. Программа должна вывести одно число — максимальную площадь четырёхугольника, удовлетворяющего условиям задачи. Если такого четырёхугольника не существует, программа должна вывести ноль. 6 0 0 2 0 0 2 3 -3 5 -5 6 6 Пример выходных данных для приведённого выше примера входных данных: 11

понятно, что нужно найти:
при у = 0 - max_x и min_x,
при y>0 - max_y и
при y<0 - min_y, если чего-то не нашли, то выводим 0.
Следует ли обрабатывать случай когда четырехугольник вырождается в треугольник?
Например, что должно быть напечатано при таких данных:
4
0 0
4 0
0 3
0 -3
0 или 12?

 Отправлено: 02.04.14 17:13. Заголовок: oval пишет: Следует ..

oval пишет:

цитата:

Следует ли обрабатывать случай когда четырехугольник вырождается в треугольник?

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

 Отправлено: 02.04.14 17:34. Заголовок: Поляков пишет: Дума..

Поляков пишет:

цитата:

Думаю, что да. В приведённом примере я бы дал ответ 12.

Что-то Вы себе противоречите
Здесь задан треугольник с вершинами в точках (4,0), (0,3), (0, -3),
4 точка (0,0) лежит на стороне (0,3), (0, -3)
тогда ответ 0.
А если прямая не перпендикулярна оси ОХ. Школьники могут проверить принадлежность трех точек одной прямой (есть ли это в программе по геометрии)?

цитата:

Но все зависит от критериев

Видимо я не совсем понимаю процедуру экзамена, когда становятся известны критерии?

 Отправлено: 02.04.14 17:38. Заголовок: oval пишет: Здесь за..

oval пишет:

цитата:

Здесь задан треугольник с вершинами в точках (4,0), (0,3), (0, -3), 4 точка (0,0) лежит на стороне (0,3), (0, -3) тогда ответ 0.

Ну а если бы четвертая точка была (-0.00001,0), тогда было бы чуть больше 12? :-) Здесь предельный случай четырехугольника с четвертой вершиной в (-eps;0) при eps->0.

 Отправлено: 02.04.14 17:52. Заголовок: согласно условию Каж..

согласно условию

цитата:

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

поэтому вариант

цитата:

(-eps;0)

не пойдет.
Так вопрос в этом и состоит: выкидывать такие вырожденные четырехугольники, или нет?
Как узнать до или во время экзамена что подразумевается под словами:

цитата:

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

или вся надежда на корректную формулировку задания в боевом варианте?

 Отправлено: 02.04.14 18:00. Заголовок: oval пишет: вся наде..

oval пишет:

цитата:

вся надежда на корректную формулировку задания в боевом варианте?

Да. К сожалению, на ЕГЭ нет возможности задать вопрос авторам задачи. Поэтому в случае, когда возможны различные трактовки, нужно просто описать те допущения, которые мы принимаем. Например, в этой задаче я бы написал так: "Программа обрабатывает особый случай, когда в левой полуплоскости нет ни одной точки, но на оси OY есть более двух точек. В этом случае считаем, что можно построить вырожденный четырехугольник, у которого три вершины лежат на оси OY". Или так: "Программа обрабатывает особый случай, когда в левой полуплоскости нет ни одной точки, но на оси OY есть более двух точек. В этом случае считаем, что требуемый четырехугольник построить нельзя." То есть, нужно надеяться на то, что эксперты увидят неоднозначность формулировки задания и в тот же время увидят, что учащийся понимает проблему.