Задача с отрезками

@Hsour · Регистрация: 30.10.2013

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

Даны координаты концов n отрезков на числовой прямой. Определить отрезок, входящий в пересечение наибольшего количества заданных отрезков.

Помогите, пожалуйста решить. Или хотя бы как её можно решить?

@Hsour · 01.11.2013, 14:09 **[ТС]**

Помогите хоть с идеей. Хотя бы как подойти к ней, с чего начать

@Puporev · 01.11.2013, 15:49

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

с чего начать

Объяви тип запись с координатами концов отрезков

Pascal
1
2
3
type otr=record
             x1,y1,x2,y2:real
            end;

объяви масив записей

Pascal
1
var a:array[1..10] of otr;

присвой значения элементам массива.
Затем в двойном цикле пройдись по массиву и сравнивай каждую пару отрезков, если один из концов внутри второго отрезка, то пересечение. Так для каждого отрезка, и ищи максимальное число пересечений.

@Hsour · 14.11.2013, 20:19 **[ТС]**

Вы не так поняли. Мне не нужно определить какое количество отрезков из заданых пересекается. Мне нужно построить, ещё один отрезок, который будет пересекать наибольшее количество заданных. Т.е. если вводится 5 отрезков, то мне нужно построить шестой. И определить самому какие координаты у него будут.

@Cyborg Drone · 14.11.2013, 22:39

Puporev,

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

на числовой прямой

Hsour, ну и, какие проблемы? Объяви тип запись с координатами концов отрезков

Pascal
1
2
3
  type otr=record
    x1, x2:real
  end;

объяви масив записей, например,

Pascal
1
  var a:array[1..10] of otr;

Потом принимаешь первый отрезок за целевой и пробегаешься по всем отрезкам. Если есть пересечение, укорачиваешь (ну или не изменяешь) отрезок, нет пересечения - удлиняешь.

@Hsour · 15.11.2013, 00:41 **[ТС]**

Прошу прощения, я лох)
Я сам не так понял суть

@Напильнег · 16.11.2013, 00:29

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

Помогите, пожалуйста решить. Или хотя бы как её можно решить?

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

Помогите хоть с идеей. Хотя бы как подойти к ней, с чего начать

Начать следует с того, что не умничать, а тупо опубликовать условие задачи полностью.

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

я лох)

Это точно.

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

Сообщение от Cyborg Drone

... ну и, какие проблемы? Объяви тип запись ...

Проблема в таких задачах обычно в том, что n может быть очень до фига плюс единица, а времени дается дэцел, и память обычно ограниченна, и все ваши (я всех вписавшихся горе-советчиков имею ввиду, поэтому с маленькой буквы, т.к. множественное число) "советы" ни на что при таких обстоятельствах не годятся.

@Cyborg Drone · 17.11.2013, 00:44

Не по теме:

Сообщение от Напильнег

"советы" ни на что при таких обстоятельствах не годятся.

Напильнег, и... Что? Вы что-то спросить хотели, или посоветовать что-нибудь? Я, одноклеточный, не понимаю мотивации Ваших действий...

@Hsour · 07.12.2013, 00:34 **[ТС]**

Сообщение от Напильнег

Начать следует с того, что не умничать, а тупо опубликовать условие задачи полностью.

Задача была опубликована полностью.
Решение уже найдено, задача написана и сдана.
Горе-советчики это вы.
Задача решается простым перебором всех отрезков и, с помощью небольшой проверки, проверки пересечений. Если пересекаются - счётчик увеличивается и в буфер идёт номер отрезка.

@Напильнег · 18.12.2013, 22:43

Сообщение от Cyborg Drone

Напильнег, и... Что? Вы что-то спросить хотели, или посоветовать что-нибудь?

Спросить хотел то что и спросил - условие задачи. Посоветовать - для начала осознать условие и вытекающие трудности.

Сообщение от Cyborg Drone

Я, одноклеточный, не понимаю мотивации Ваших действий...

Сеять разумное, доброе, вечное, и все такое. Одноклеточным действительно не понять...

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

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

Задача была опубликована полностью.
Решение уже найдено, задача написана и сдана.

То, что задача сдана, не значит, что она решена.

И что, Ваше решение будет работать, если задать n в миллиард? Ограничений то мы так и не увидели.

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

Горе-советчики это вы.

"Вы" с маленькой буквы - это когда обращаются ко множественному числу - имейте в виду.

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

Задача решается простым перебором всех отрезков

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

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

и, с помощью небольшой проверки, проверки пересечений. Если пересекаются - счётчик увеличивается и в буфер идёт номер отрезка.

Бред какой-то. То ли Вы так "умеете" свои мысли излагать, то-ли решается совсем другая задача.

Новые блоги и статьи Все статьи Все блоги /
Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .

@Hsour 0 / 0 / 0 Регистрация: 30.10.2013 Сообщений: 6

	Задача с отрезками 30.10.2013, 18:47. Показов 2546. Ответов 9 Метки нет (Все метки) Даны координаты концов n отрезков на числовой прямой. Определить отрезок, входящий в пересечение наибольшего количества заданных отрезков. Помогите, пожалуйста решить. Или хотя бы как её можно решить? 0

@Hsour 0 / 0 / 0 Регистрация: 30.10.2013 Сообщений: 6
	01.11.2013, 14:09 [ТС]
	Помогите хоть с идеей. Хотя бы как подойти к ней, с чего начать 0

@Hsour 0 / 0 / 0 Регистрация: 30.10.2013 Сообщений: 6
	14.11.2013, 20:19 [ТС]
	Вы не так поняли. Мне не нужно определить какое количество отрезков из заданых пересекается. Мне нужно построить, ещё один отрезок, который будет пересекать наибольшее количество заданных. Т.е. если вводится 5 отрезков, то мне нужно построить шестой. И определить самому какие координаты у него будут. 0

@Hsour 0 / 0 / 0 Регистрация: 30.10.2013 Сообщений: 6
	15.11.2013, 00:41 [ТС]
	Прошу прощения, я лох) Я сам не так понял суть 0