Автор | Сообщение |
|
| постоянный участник
|
Сообщение: 245
|
|
Отправлено: 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?
|
|
|
Ответов - 5
[только новые]
|
|
|
| Администратор
|
Сообщение: 659
|
|
Отправлено: 02.04.14 17:13. Заголовок: oval пишет: Следует ..
oval пишет: цитата: | Следует ли обрабатывать случай когда четырехугольник вырождается в треугольник? |
|
Думаю, что да. В приведённом примере я бы дал ответ 12. Но все зависит от критериев. Лучше это оговорить в текстовом пояснении для экспертов.
|
|
|
|
| постоянный участник
|
Сообщение: 248
|
|
Отправлено: 02.04.14 17:34. Заголовок: Поляков пишет: Дума..
Поляков пишет: цитата: | Думаю, что да. В приведённом примере я бы дал ответ 12. |
| Что-то Вы себе противоречите Здесь задан треугольник с вершинами в точках (4,0), (0,3), (0, -3), 4 точка (0,0) лежит на стороне (0,3), (0, -3) тогда ответ 0. А если прямая не перпендикулярна оси ОХ. Школьники могут проверить принадлежность трех точек одной прямой (есть ли это в программе по геометрии)? цитата: | Но все зависит от критериев |
| Видимо я не совсем понимаю процедуру экзамена, когда становятся известны критерии?
|
|
|
|
| Администратор
|
Сообщение: 660
|
|
Отправлено: 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.
|
|
|
|
| постоянный участник
|
Сообщение: 249
|
|
Отправлено: 02.04.14 17:52. Заголовок: согласно условию Каж..
согласно условию цитата: | Каждая из следующих N строк содержит два целых числа: сначала координата x, затем координата y очередной точки. |
|
поэтому вариант не пойдет. Так вопрос в этом и состоит: выкидывать такие вырожденные четырехугольники, или нет? Как узнать до или во время экзамена что подразумевается под словами: цитата: | Если такого четырёхугольника не существует, программа должна вывести ноль. |
| или вся надежда на корректную формулировку задания в боевом варианте?
|
|
|
|
| Администратор
|
Сообщение: 661
|
|
Отправлено: 02.04.14 18:00. Заголовок: oval пишет: вся наде..
oval пишет: цитата: | вся надежда на корректную формулировку задания в боевом варианте? |
|
Да. К сожалению, на ЕГЭ нет возможности задать вопрос авторам задачи. Поэтому в случае, когда возможны различные трактовки, нужно просто описать те допущения, которые мы принимаем. Например, в этой задаче я бы написал так: "Программа обрабатывает особый случай, когда в левой полуплоскости нет ни одной точки, но на оси OY есть более двух точек. В этом случае считаем, что можно построить вырожденный четырехугольник, у которого три вершины лежат на оси OY". Или так: "Программа обрабатывает особый случай, когда в левой полуплоскости нет ни одной точки, но на оси OY есть более двух точек. В этом случае считаем, что требуемый четырехугольник построить нельзя." То есть, нужно надеяться на то, что эксперты увидят неоднозначность формулировки задания и в тот же время увидят, что учащийся понимает проблему.
|
|
|
|