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

@SunriseD · Регистрация: 29.09.2019

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

Утро доброе, готовлюсь к экзамену в данный момент, а преподаватель не давал на несколько тем по с++
Хочу понять как решать эту задачу, вроде выглядит просто, но в голове не укладывается, вы сами понимаете
Задача:
На плоскости дан набор точек с целочисленными координатами. Необходимо найти такой треугольник наибольшей площади с вершинами в этих точках, у которого нет общих точек с осью Оу, а одна из сторон лежит на оси Ох.

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

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

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

В первой строке вводится одно целое положительное число — количество точек N.

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

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

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

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

8

-10 0

2 0

0 4

3 3

7 0

5 5

4 0

9 -9

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

22 . 5

Заранее огромное спасибо, Вам!

@Annemesski · 30.06.2020, 11:34

Подскажу:
1. определим структуру "точка" с полями содержащими координату по Х и по У
2. объявим массив структур типа "точка" из трех элементов.

далее: представим треугольник АВС (вершина А - нулевой элемент массива точек, В и С соответственно первый и второй), пусть сторона ВС образует его основание - которое, по условию задачи, должно лежать на оси абсцисс, тогда:
3. проинициализируем массив точек значениями заведомо не удовлетворяющими искомому треугольнику, например: вершина А лежит в начале координат (нарушаем условие отсутствия общих точек у треуголника и ординаты), а вершины В и С в точке (1,1) - основание не принадлежит оси абсцисс равно как и две других стороны.
4. организуем ввод точек и:
если точка имеет координату Х == 0 - игнорируем такую точку ибо она гарантирует общую точку с осью ординат;
если точка имеет координату У == 0 и лежит справа от точки В по абсциссе, то это вершина В;
если У == 0 и по абсциссе находится слева от С, то это вершина С
5. по окончании ввода анализируем массив следующим образом:
5.1 ни одна вершина не может иметь координату Х равную 0;
5.2 все вершины должны находиться в одной стороне от ординаты, то есть у всех трех вершин координата Х либо положительна, либо отрицательна
5.3 вершины В и С обязаны иметь координату У равную 0.

Следовательно: если условия пункта 5 удовлетворены, то рассчитываем площадь треугольника по формуле Герона, иначе выводим 0.

Байт · 30.06.2020, 12:00

Искомый треугольник обладает такими свойствами. Есть 2 точки с y=0 и x1*x2 > 0 (т.е они одного знака). Его вершина должна иметь тот же x-знак и иметь максимальный по модулю y. Отрезок [x1, x2] тоже должен иметь максимальную длину. Для определения этих вещей совсем не обязательно хранить в памяти все точки. Достаточно завести несколько переменных
yR - максимальный по модулю y точки в правой полуплоскости ( x > 0)
yL - тоже для левой полуплоскости
x1R, x2R - Максимальный и минимальный x для точек с y = 0 в правой полуплоскости
x1L, x2L - тоже для левой.
В процессе ввода надо отслеживать обновление значений этих переменных.
А затем посчитать максимальную площадь (или определить отсутствие треугольника с такими свойствами)

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

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

по формуле Герона,

Простите, но Герон пусть отдохнет. Одна из сторон лежит на оси Х. Поэтому площадь считается много проще. По формуле
S = 0.5*основание*высота

Добавлено через 7 минут
Annemesski, Наши с вами подходы, в общем-то похожи, отличаются некоторыми деталями и у вас чуток подробнее.
Зато у вас про Y ничего нет.
В обоих случаях набросана только схема решения, а уж реализовать это в коде ТС придется самому. Впрочем, постановка задачи как бы предполагает, что у ТС есть уже некоторые навыки.

@Annemesski · 30.06.2020, 12:36

Герон пусть отдохнет

Ваша правда.

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

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

Зато у вас про Y ничего нет.

а что там про У, имея остальные условия остается только одно ограничение: ни одна из вершин не может иметь У == 0

реализовать это в коде ТС придется самому.

разумеется, готовится к программированию пусть его и практикует, математику разжевали, алгоритм показали

мда, и опять косяк с проверкой ввода для вершин В и С остался, надо чуток подумать.

Добавлено через 10 минут
с В и С надо так: первая введенная точка удовлетворяющая условию У == 0 инициализирует и В и С, а далее точка левее В и С обновляет значение В, те что правее обновляют С

и еще сморозил

ни одна из вершин не может иметь У == 0

по У вовсе нет никаких ограничений, кроме того, что для В и С У строго равен 0

@Kuzia domovenok · 30.06.2020, 14:36

Байт, как ты так быстро за 26 мин ответил Annemesski с выкладками про yR, yL, x1R, x2R и всем вот этим?

Байт · 30.06.2020, 16:47

Не по теме:

Сообщение от Kuzia domovenok

Байт, как ты так быстро за 26 мин ответил Annemesski

Я писал свой пост №3 когда ответа в посте 2 еще не было
А время поста, видимо, равно времени последней правки

Добавлено через 19 минут
Попробуем начать.

C++
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
typedef struct {
  int y, x1, x2;
} T;
void Osn(T &L, T &R, int x) {
  // ...
}
void Ver(T &L, T &R, int y, int x) {
   if (x < 0) {
     L.y = max(abs(y), L.y));
   if (x > 0) {
     R.y = max(abs(y), R.y));
}
int Plat(T &X) 
{
   if (X.y==0 || X.x1==0 || X.x2==0) return 0;
   return abs(X.x1 - X.x2)*X.y;
}
int main()
{ int n, x, y;
  T R = {0}, L = {0};
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> x >> y;
    if (y==0) 
     Osn(L, R,  x);
    else 
     Ver(L, R, y, x);
  }
   int SR = Plat(R);
   int SL = Plat(L);
   cout << max(SR, SL)/2.0;
   return 0;
}

Осталось функцию Osn дописать...
ЗЫ. Не проверял, возможно все.

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// x1 < x2
void Osn(T &L, T &R, int x) {
  if (x==0) return;
  T *p = (x >0) : &R : &L;
  x = abs(x);
  if (p->x1==0) p->x1= x;
  else {
    if (p->x2==0) {
      if (x >= p->x1) p->x2 = x;
      else {
         p->x2 = p->x1;
         p->x1 = x;
      }
    }
    else {
      if (x<p->x1) p->x1 = x;
      if (x> p->x2) p->x2 = x;
   }
}

@TheCalligrapher · 30.06.2020, 17:47

Del

Новые блоги и статьи Все статьи Все блоги /
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 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии 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 позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@SunriseD 0 / 0 / 0 Регистрация: 29.09.2019 Сообщений: 15

	Найти треугольник наибольшей площади, у которого нет общих точек с осью Оу, а одна из сторон лежит на оси Ох 30.06.2020, 10:01. Показов 2703. Ответов 6 Метки c++ (Все метки) Утро доброе, готовлюсь к экзамену в данный момент, а преподаватель не давал на несколько тем по с++ Хочу понять как решать эту задачу, вроде выглядит просто, но в голове не укладывается, вы сами понимаете Задача: На плоскости дан набор точек с целочисленными координатами. Необходимо найти такой треугольник наибольшей площади с вершинами в этих точках, у которого нет общих точек с осью Оу, а одна из сторон лежит на оси Ох. Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Размер памяти, которую использует Ваша программа, не должен зависеть от количества точек. Перед текстом программы кратко опишите используемый алгоритм решения задачи и укажите используемый язык программирования и его версию. Описание входных данных В первой строке вводится одно целое положительное число — количество точек N. Каждая из следующих N строк содержит два целых числа — сначала координата х, затем координата у очередной точки. Числа разделены пробелом. Описание выходных данных Программа должна вывести одно число — максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль. Пример входных данных: 8 -10 0 2 0 0 4 3 3 7 0 5 5 4 0 9 -9 Пример выходных данных для приведённого выше примера входных данных: 22 . 5 Заранее огромное спасибо, Вам! 0

@Annemesski 2673 / 1335 / 480 Регистрация: 08.11.2016 Сообщений: 3,690
	30.06.2020, 11:34
	Подскажу: 1. определим структуру "точка" с полями содержащими координату по Х и по У 2. объявим массив структур типа "точка" из трех элементов. далее: представим треугольник АВС (вершина А - нулевой элемент массива точек, В и С соответственно первый и второй), пусть сторона ВС образует его основание - которое, по условию задачи, должно лежать на оси абсцисс, тогда: 3. проинициализируем массив точек значениями заведомо не удовлетворяющими искомому треугольнику, например: вершина А лежит в начале координат (нарушаем условие отсутствия общих точек у треуголника и ординаты), а вершины В и С в точке (1,1) - основание не принадлежит оси абсцисс равно как и две других стороны. 4. организуем ввод точек и: если точка имеет координату Х == 0 - игнорируем такую точку ибо она гарантирует общую точку с осью ординат; если точка имеет координату У == 0 и лежит справа от точки В по абсциссе, то это вершина В; если У == 0 и по абсциссе находится слева от С, то это вершина С 5. по окончании ввода анализируем массив следующим образом: 5.1 ни одна вершина не может иметь координату Х равную 0; 5.2 все вершины должны находиться в одной стороне от ординаты, то есть у всех трех вершин координата Х либо положительна, либо отрицательна 5.3 вершины В и С обязаны иметь координату У равную 0. Следовательно: если условия пункта 5 удовлетворены, то рассчитываем площадь треугольника по формуле Герона, иначе выводим 0. 1

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	30.06.2020, 14:36
	Байт, как ты так быстро за 26 мин ответил Annemesski с выкладками про yR, yL, x1R, x2R и всем вот этим? 0

@TheCalligrapher Вездепух 12938 / 6805 / 1821 Регистрация: 18.10.2014 Сообщений: 17,227
	30.06.2020, 17:47
	Del 0

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

Решение