Форум » Обработка числовых последовательностей » Задача с http://inf.reshuege.ru » Ответить
Задача с http://inf.reshuege.ru
oval: C 4 № 6906. [quote] На плоскости дан набор точек с целочисленными координатами. Необходимо найти четырёхугольник наибольшей площади с вершинами в этих точках, две вершины которого лежат на оси Oy, а две оставшиеся — по разные стороны от оси Oy. Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Описание входных данных. В первой строке вводится одно целое положительное число — количество точек N. Каждая из следующих N строк содержит два целых числа: сначала координата x, затем координата y очередной точки. Описание выходных данных. Программа должна вывести одно число — максимальную площадь четырёхугольника, удовлетворяющего условиям задачи. Если такого четырёхугольника не существует, программа должна вывести ноль. 6 0 0 2 0 0 2 3 -3 5 -5 6 6 Пример выходных данных для приведённого выше примера входных данных: 11[/quote] понятно, что нужно найти: при у = 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?
Ответов - 5
Поляков: oval пишет: Следует ли обрабатывать случай когда четырехугольник вырождается в треугольник? Думаю, что да. В приведённом примере я бы дал ответ 12. Но все зависит от критериев. Лучше это оговорить в текстовом пояснении для экспертов.
oval: Поляков пишет: Думаю, что да. В приведённом примере я бы дал ответ 12. Что-то Вы себе противоречите Здесь задан треугольник с вершинами в точках (4,0), (0,3), (0, -3), 4 точка (0,0) лежит на стороне (0,3), (0, -3) тогда ответ 0. А если прямая не перпендикулярна оси ОХ. Школьники могут проверить принадлежность трех точек одной прямой (есть ли это в программе по геометрии)? Но все зависит от критериев Видимо я не совсем понимаю процедуру экзамена, когда становятся известны критерии?
Поляков: oval пишет: Здесь задан треугольник с вершинами в точках (4,0), (0,3), (0, -3), 4 точка (0,0) лежит на стороне (0,3), (0, -3) тогда ответ 0. Ну а если бы четвертая точка была (-0.00001,0), тогда было бы чуть больше 12? :-) Здесь предельный случай четырехугольника с четвертой вершиной в (-eps;0) при eps->0.
oval: согласно условию Каждая из следующих N строк содержит два целых числа: сначала координата x, затем координата y очередной точки. поэтому вариант (-eps;0) не пойдет. Так вопрос в этом и состоит: выкидывать такие вырожденные четырехугольники, или нет? Как узнать до или во время экзамена что подразумевается под словами: Если такого четырёхугольника не существует, программа должна вывести ноль. или вся надежда на корректную формулировку задания в боевом варианте?
Поляков: oval пишет: вся надежда на корректную формулировку задания в боевом варианте? Да. К сожалению, на ЕГЭ нет возможности задать вопрос авторам задачи. Поэтому в случае, когда возможны различные трактовки, нужно просто описать те допущения, которые мы принимаем. Например, в этой задаче я бы написал так: "Программа обрабатывает особый случай, когда в левой полуплоскости нет ни одной точки, но на оси OY есть более двух точек. В этом случае считаем, что можно построить вырожденный четырехугольник, у которого три вершины лежат на оси OY". Или так: "Программа обрабатывает особый случай, когда в левой полуплоскости нет ни одной точки, но на оси OY есть более двух точек. В этом случае считаем, что требуемый четырехугольник построить нельзя." То есть, нужно надеяться на то, что эксперты увидят неоднозначность формулировки задания и в тот же время увидят, что учащийся понимает проблему.
полная версия страницы