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

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

05.11.2017, 18:17. Просмотров 2107. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.11.2017, 18:17
Ответы с готовыми решениями:

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

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

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

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

7
6817 / 5958 / 2708
Регистрация: 14.04.2014
Сообщений: 25,504
05.11.2017, 18:34 2
Что за два ряда цифр? Как он объявлен?
0
0 / 0 / 0
Регистрация: 17.05.2016
Сообщений: 56
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
6817 / 5958 / 2708
Регистрация: 14.04.2014
Сообщений: 25,504
06.11.2017, 17:05 4
И как хочешь сортировать? От условия зависит.
0
0 / 0 / 0
Регистрация: 17.05.2016
Сообщений: 56
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
6817 / 5958 / 2708
Регистрация: 14.04.2014
Сообщений: 25,504
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
0 / 0 / 0
Регистрация: 17.05.2016
Сообщений: 56
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
6817 / 5958 / 2708
Регистрация: 14.04.2014
Сообщений: 25,504
11.11.2017, 20:40 8
Как удалить, что ли? erase().
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.11.2017, 20:40

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

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

Определить попарно номера окружностей, которые имеют хотя бы одну общую точку
Пересекающиеся окружности. Даны натуральные числа 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 - 2020, vBulletin Solutions, Inc.