Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
Qitelery
0 / 0 / 0
Регистрация: 17.05.2016
Сообщений: 44
1

По заданным отрезкам найти множество для которого каждый из отрезков содержит хотя бы одну точку

05.11.2017, 18:17. Просмотров 735. Ответов 7
Метки нет (Все метки)

Здравствуйте! Пожалуйста подскажите, что если дан массив, например, следующий:
[1]4 7
[2]1 3
[3]2 5
[4]5 6

1) Я применяю к нему сортировку
C++
1
sort(segments.begin(), segments.end());
как он будет выглядеть после этой сортировки?

2) Мне надо выкинуть из него два значения и оставить [2] и [4]. Так чтобы и длинна его тоже стала равна 2.

Спасибо!
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2017, 18:17
Ответы с готовыми решениями:

Дано множество отрезков на прямой. Найти множество точек, принадлежащих хотя бы двум из них
Здравствуйте. Задача поставлена как в заголовке темы. Отрезки записаны в фале(начало, конец), их...

Дано множество отрезков; найти отрезок, середина которого ближе всего к заданной точке
Дано множество отрезков. Среди отрезков, длина которых больше D, найти отрезок, середина которого...

Найти количество слов, которое содержит хотя бы одну букву 'А'
Дана строка состоящая из русских слов набранных заглавными буквами и разделенными пробелами.Найти...

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

Содержит ли число N хотя бы одну цифру M?
Доброго времени суток, господа! Как я уже и говорил, только начинаю изучать программирование. На...

7
nmcf
6527 / 5751 / 2621
Регистрация: 14.04.2014
Сообщений: 24,493
05.11.2017, 18:34 2
Что за два ряда цифр? Как он объявлен?
0
Qitelery
0 / 0 / 0
Регистрация: 17.05.2016
Сообщений: 44
06.11.2017, 15:05  [ТС] 3
nmcf, так ну в общем задание такое

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

В первой строке дано число 1≤n≤100 отрезков. Каждая из последующих nn строк содержит по два числа 0≤l≤r≤10^9, задающих начало и конец отрезка. Выведите оптимальное число mm точек и сами mm точек. Если таких множеств точек несколько, выведите любое из них.

Там еще код дан, в который надо вписать свой и я думаю над тем как правильно отсортировать и сформировать вектор из нужных значений.

На всякий случай вот код (код задания изменять запрещается):

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
34
35
#include <iostream>
#include <utility>
#include <vector>
 
using namespace std;
 
using Segment = std::pair<int, int>;
 
std::vector <int> get_covering_set(std::vector <Segment> segments) {
  std::vector <int> result;
   
  // put your code
    
  for (auto s : segments) {
    result.push_back(s.second);
  }
 
  return result;
}
 
int main(void) {
  int segments_count;
  std::cin >> segments_count;
  std::vector <Segment> segments(segments_count);
  for (auto &s:segments) {
    std::cin >> s.first >> s.second;
  }
 
  auto points = get_covering_set(std::move(segments));
  std::cout << points.size() << std::endl;
  for (auto point:points) {
    std::cout << point << " ";
  }
  std::cout << std::endl;
}
0
nmcf
6527 / 5751 / 2621
Регистрация: 14.04.2014
Сообщений: 24,493
06.11.2017, 17:05 4
И как хочешь сортировать? От условия зависит.
0
06.11.2017, 17:05
Qitelery
0 / 0 / 0
Регистрация: 17.05.2016
Сообщений: 44
11.11.2017, 12:59  [ТС] 5
Хочу отсортировать по правому значению.
Т.е. если дано
[1]4 7
[2]1 3
[3]2 5
[4]5 6
то после сортировки должно быть
[2]1 3
[3]2 5
[4]5 6
[1]4 7
0
nmcf
6527 / 5751 / 2621
Регистрация: 14.04.2014
Сообщений: 24,493
11.11.2017, 13:26 6
C++
1
sort(segments.begin(), segments.end(), [](const Segment &a, const Segment &b){ return a.second < b.second; });
1
Qitelery
0 / 0 / 0
Регистрация: 17.05.2016
Сообщений: 44
11.11.2017, 16:35  [ТС] 7
nmcf, вот тут есть строчка

C++
1
2
3
4
5
for (auto s : segments) {
    result.push_back(s.second);
  }
 
  return result;
Насколько я понял, нужно в конечно счете исключить из segment значения, которые пересекаются, т.е. оставить какие-то один из них. Имею в виду, что если
[2]1 3
[3]2 5
[4]5 6
[1]4 7
то оставить в segment
[2]1 3
[3]2 5
И вот их запишут в result.
Вопрос. Допустим я сделаю парсинг и найду этим пары значений. Как мне из вектора состоящего из 4 значений сделать, состоящий из двух?
0
nmcf
6527 / 5751 / 2621
Регистрация: 14.04.2014
Сообщений: 24,493
11.11.2017, 20:40 8
Как удалить, что ли? erase().
1
11.11.2017, 20:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2017, 20:40

Определить попарно номера окружностей, которые имеют хотя бы одну общую точку
Пересекающиеся окружности. Даны натуральные числа x1,y1,r1...,x(n),y(n),r(n), которые задают...

Заданы N отрезков с координатами концов. Принадлежность точки отрезкам.
Вообщем не пойму саму суть определения... const n=3; var i,x,k:integer; a,b:array of real;...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru