Задача про треугольник с наибольшей площадью (Паскаль)

@Roman Chervakov · Регистрация: 30.06.2020

Студворк — интернет-сервис помощи студентам

На плоскости дан набор точек с целочисленными координатами. Необходимо найти такой треугольник наибольшей площади с вершинами в этих точках, у которого нет общих точек с осью Оу, а одна из сторон лежит на оси Ох. Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Размер памяти, которую использует Ваша программа, не должен зависеть от количества точек. Перед текстом программы кратко опишите используемый алгоритм решения задачи и укажите используемый язык программирования и его версию.

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

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

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

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

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

8

-10 0

2 0

0 4

3 3

7 0

5 5

4 0

9 -9

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

22 . 5

Решение на языке Паскаль. Если учитель спросит, то все переменные с индексом 1 ищут треугольник в первой и четвертой координатных четвертях, а с индексом 2 во второй и третьей, а потом в конце сравниваются два треугольника и выводится площадь большего из них, если же треугольник не нашелся вообще, то в любом случае выведется ноль, ведь всем максимальным Y в начале присвоен 0, а в случае равенства максимального и минимального X все обратиться в ноль, и в итоге на него умножится и ответом будет ноль, все предусмотрено!

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var x, y, i, N, mnx1, mxx1, mxy1, mnx2, mxx2, mxy2: integer;
 
begin readln(N); mnx1:=maxint; mxx1:=0; mxy1:=0; mnx2:=maxint; mxx2:=0; mxy2:=0;
 
for i:=1 to N do
begin
 
readln(x,y);
if (x>0) then
begin
x:=abs(x); y:=abs(y);
if (y=0) then
begin
if x>mxx1 then mxx1:=x;
if x<mnx1 then mnx1:=x;
end;
if (x*y <> 0) and (y > mxy1) then mxy1:=y;
end;
if (x<0) then
begin
x:=abs(x); y:=abs(y);
if (y=0) then
begin
if x>mxx2 then mxx2:=x;
if x<mnx2 then mnx2:=x;
end;
if (x*y <> 0) and (y > mxy2) then mxy2:=y;
end;
 
end;
 
if (mxx1-mnx1) > (mxx2-mnx2) then writeln((mxx1-mnx1)*mxy1/2) else
writeln((mxx2-mnx2)*mxy2/2);
 
end.

@JuriiMW · 01.07.2020, 04:53

Ну вот для вашей программы ввожу:
3
1 0
1 2
2 1
А она мне в ответ 0.
Чего-то не то!

@mr-Crocodile · 02.07.2020, 09:57

Сообщение от JuriiMW

Ну вот для вашей программы ввожу:

точка

Сообщение от JuriiMW

1 0

лежит на оси ординат 0Y, что нарушает правило

Сообщение от Roman Chervakov

с вершинами в этих точках, у которого нет общих точек с осью Оу,

@Puporev · 02.07.2020, 10:20

Сообщение от Roman Chervakov

у которого нет общих точек с осью Оу, а одна из сторон лежит на оси Ох.

Я так понимаю что нужно найти такие треугольники у которых все точки лежат по одну сторону от оси Y, и 2 точки лежат на оси Х.

@JuriiMW · 02.07.2020, 10:39

Сообщение от mr-Crocodile

1 0
лежит на оси ординат 0Y,

Вот те раз!
Эта точка лежит на оси абсцисс.
На оси ординат лежат точки, у которых на месте x всегда 0.

@mr-Crocodile · 02.07.2020, 10:45

Сообщение от Puporev

ужно найти такие треугольники у которых все точки лежат по одну сторону от оси Y, и 2 точки лежат на оси Х.

в точку!
поэтому у вершин треугольника все координаты X должны быть одного знака,
а у двух вершин из трёх координата координаты Y должны быть равны нулю.

Добавлено через 3 минуты

Сообщение от JuriiMW

Эта точка лежит на оси абсцисс.

а, точно, я был не прав!

Добавлено через 1 минуту
JuriiMW,

Сообщение от JuriiMW

1 0
1 2
2 1

тут нарушение второго условия

Сообщение от Roman Chervakov

а одна из сторон лежит на оси Ох.

@JuriiMW · 02.07.2020, 10:47

mr-Crocodile, ну и у меня тоже не всё в порядке с данными… ;–(

@кот Бегемот · 03.07.2020, 00:19

Сообщение от Puporev

Я так понимаю что нужно найти такие треугольники у которых все точки лежат по одну сторону от оси Y, и 2 точки лежат на оси Х.

Это ещё почему? Точки могут лежать где угодно, главное найти наибольшее расстояние между точками на оси х и наибольшую ординату.

Сообщение от mr-Crocodile

в точку!
поэтому у вершин треугольника все координаты X должны быть одного знака,

Брехня.
На площадь треугольника знак числа никак не влияет

Решение простое: ищем точки, у которых у=0 с минимальным и максимальным х, точку с максимальным по модулю у и ответ готов.

@Puporev · 03.07.2020, 08:32

Сообщение от кот Бегемот

Это ещё почему?

Потому что

у которого(у треугольника) нет общих точек с осью

по моему означает что ни одна из сторон не должна пересекать ось Y.

@кот Бегемот · 03.07.2020, 09:24

Да, видимо, ошибся. Просто здесь уже была похожая задача, только без пересечения с у.

@Roman Chervakov · 04.07.2020, 13:14 **[ТС]**

Привет, внимательнее прочитай задачу, во входных данных, которые ты предлагаешь лишь одна точка, лежащая на оси X, поэтому программа не может найти треугольник.

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@JuriiMW 5095 / 2661 / 2355 Регистрация: 10.12.2014 Сообщений: 10,060
	01.07.2020, 04:53
	Ну вот для вашей программы ввожу: 3 1 0 1 2 2 1 А она мне в ответ 0. Чего-то не то! 0

@JuriiMW 5095 / 2661 / 2355 Регистрация: 10.12.2014 Сообщений: 10,060
	02.07.2020, 10:47
	mr-Crocodile, ну и у меня тоже не всё в порядке с данными… ;–( 0

@кот Бегемот Платежеспособный зверь 8966 / 4389 / 1655 Регистрация: 28.10.2009 Сообщений: 11,647
	03.07.2020, 09:24
	Да, видимо, ошибся. Просто здесь уже была похожая задача, только без пересечения с у. 0

@Roman Chervakov 0 / 0 / 0 Регистрация: 30.06.2020 Сообщений: 3
	04.07.2020, 13:14 [ТС]
	Привет, внимательнее прочитай задачу, во входных данных, которые ты предлагаешь лишь одна точка, лежащая на оси X, поэтому программа не может найти треугольник. 0