Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.93/15: Рейтинг темы: голосов - 15, средняя оценка - 4.93
1 / 1 / 1
Регистрация: 05.12.2011
Сообщений: 39
1

найти точку, принадлежащую

11.01.2012, 23:00. Показов 2935. Ответов 17
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
дано множество отрезков на прямой. найти точку, которая принадлежит наибольшему количеству отрезков, определить это количество
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 11.01.2012, 23:00
Ответы с готовыми решениями:

Найти точку принадлежащую прямой
Имею координаты двух точек, нужно найти точку, которая принадлежит этой прямой. Точка должна быть...

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

Найти точку D, симметричную точку A относительно стороны BC.
помогите решить пожалуйста...

Продолжать ввод, пока не получит точку, принадлежащую графику
Есть программа, которая определяет принадлежность точки графику Сам код: #include <stdio.h>...

17
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
11.01.2012, 23:49 2
slava0394, Какие-то усилия прикладывали? В чем сложности? Ваши наработки?
0
1 / 1 / 1
Регистрация: 05.12.2011
Сообщений: 39
11.01.2012, 23:58  [ТС] 3
у меня плохо с программрованием. не знаю вообще с чего здесь начать
0
Программист
33 / 33 / 8
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
12.01.2012, 00:01 4
Ну алгоритмически то вы можете рассказать вашу версию?(задание то уж совсем простое), тогда как минимум с меня код=)
0
1 / 1 / 1
Регистрация: 05.12.2011
Сообщений: 39
12.01.2012, 00:05  [ТС] 5
объснте мне плиз. для вас оно простое, а для того кто программированием только с этого года вообще стал заниматься сложновато немного. может знаете хороший источник теории?
0
Программист
33 / 33 / 8
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
12.01.2012, 00:21 6
Это не программирование, это школьная математика=\
Ну сами подумайте - пускай у нас есть дискретный отрезок конечной длины, на нём заданы другие отрезки(так же конечной длинны) и нужно найти точку которая принадлежит наибольшему количеству отрезков...

Я вас уверяю, если вы подумаете хотя бы в течении минуты то поймёте алгоритм решения, и тогда я вам помогу с тяжёлым для вас пока программированием и напишу код.
2
1 / 1 / 1
Регистрация: 05.12.2011
Сообщений: 39
12.01.2012, 10:18  [ТС] 7
ну по идее это середина отрезка
0
Эксперт С++
5043 / 2622 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 1
12.01.2012, 10:40 8
Цитата Сообщение от slava0394 Посмотреть сообщение
ну по идее это середина отрезка
Смотря как расположены отрезки.
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
12.01.2012, 11:40 9
Я бы взял концы всех отрезков, и посмотрел бы какому количеству других отрезков они принадлежат.
Условие принадлежности точки x отрезку [a,b]: a <= x <= b
0
Программист
33 / 33 / 8
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
12.01.2012, 13:27 10
Первое что мне пришло на ум - это просто пробежаться по каждой точке отрезка и проверить её на равенство a <= x <= b для каждого из подотрезков, считая параллельно для точки число таких пересечений.
Так можно найти не только точку с максимальным количеством пересечений, но и отрезок, но тк нужна только одна точка, то на мой взгляд выглядеть это будет как-то так:
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
36
37
38
39
40
41

#include <iostream>
using namespace std;
 
pair <int, int> segm;
int len, num;
 
int main ()
{
    setlocale(LC_ALL, "");
    cout << "Введите длину основного отрезка: " << endl; cin >> len;
    len++; // Ввели 6, получили отрезок от 0 до 6 включительно.
    segm.first = 0; 
    segm.second = len;
    cout << "Введите число отрезков которые включает в себя основной: " << endl; cin >> num;
    pair <int, int> *vs = new pair <int, int> [num];
    for (int i = 0, buf = 0; i < num; i++)
    {
        cout << "Начало " << i + 1 << " отрезка: "; cin >> buf;
        if (buf >= segm.first && buf <= segm.second) vs[i].first = buf;
        cout << "Конец " << i + 1 << " отрезка: "; cin >> buf;
        if (buf >= segm.first && buf <= segm.second) vs[i].second = buf;
    }
    
    int *count = new int [len]; // Для подсчёта числа пересечений в данной точке
    int inmax = 0, nmax = 0;
 
    for (int i = 0; i < len; i++)
    {
        count[i] = 0;
        for (int j = 0; j < num; j++)
        {
            if (i >= vs[j].first &&  i <= vs[j].second) count[i] ++;
        }
        if (nmax < count[i]) { nmax = count[i]; inmax = i;}
 
        cout  << " count = " << count[i] << endl;
    }
    cout << "Максимальное число пересечений в точке " << inmax << " равно " << nmax << endl;
 
    system("pause");
}
1
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
12.01.2012, 13:33 11
Цитата Сообщение от Whiteha Посмотреть сообщение
это просто пробежаться по каждой точке отрезка
Любопытно, как вы собираетесь пробежаться по континуму ?
0
Программист
33 / 33 / 8
Регистрация: 08.07.2011
Сообщений: 190
Записей в блоге: 1
12.01.2012, 13:53 12
Я исходил из дискретности отрезка, автор ведь не указал какому множеству принадлежит отрезок и я выдвинул самую простую версию. Хотя конечно не самую универсальную.=)
0
1 / 1 / 1
Регистрация: 05.12.2011
Сообщений: 39
12.01.2012, 14:10  [ТС] 13
жесть
0
22 / 22 / 16
Регистрация: 22.08.2011
Сообщений: 79
12.01.2012, 14:16 14
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include "stdafx.h"
 
#include <stdio.h>
#include <stdlib.h>
 
int main (void)
{
    int mas[2][6]= {{1,2,3,4,5,6},{3,4,5,6,7,3}};
    int count =0, k; 
    for(int i =0;i<6;i++)
    {   
        int x= mas[0][i], tmpCount=0;
        for(int j =0;j<6;j++)
        {
            if(mas[1][j] >= x && x<=mas[2][j]) tmpCount++;
        }
        if(count < tmpCount) {count = tmpCount;k = x;}
    }
    printf("%d   %d", k, count);
    scanf("%d",&k);
}
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
12.01.2012, 15:29 15
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

/////////////////////////////////////////////////////////////////////////////////////////
//Дано множество отрезков на прямой. Найти точку, которая принадлежит наибольшему 
//количеству отрезков, определить это количество.
/////////////////////////////////////////////////////////////////////////////////////////
#include <complex>
#include <iostream>
#include <map>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef double                          T_coord;
typedef std::complex    <T_coord>       T_segment;
typedef std::vector     <T_segment>     T_segments;
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_counters
{    
    int  left_counter_;
    int  right_counter_;
    //-----------------------------------------------------------------------------------
    T_counters()
        :
        left_counter_   (),
        right_counter_  ()
    {}
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::map<T_coord, T_counters>   T_segm_end_points;
/////////////////////////////////////////////////////////////////////////////////////////
void  fill_segm_end_points
    (
        const T_segments&   segments,
        T_segm_end_points&  segm_end_points
    )
 
{
    for(
        T_segments::const_iterator  segm_it = segments.begin();
        segm_it != segments.end();
        ++segm_it
       )
    {
        ++segm_end_points[segm_it->real()].left_counter_;
        ++segm_end_points[segm_it->imag()].right_counter_;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
void  get_max_segm_counter_and_max_segm_counter_point
    (
        const T_segments&   segments,
        int&                max_segm_counter,
        T_coord&            max_segm_counter_point    
    )
{
    T_segm_end_points  segm_end_points;
 
    fill_segm_end_points
        (
            segments,
            segm_end_points
        );
 
    int  cur_segm_counter = 0;
 
    for(
        T_segm_end_points::iterator  
        segm_end_point_it = segm_end_points.begin();
        segm_end_point_it != segm_end_points.end();
        ++segm_end_point_it
       )
    {
        cur_segm_counter += segm_end_point_it->second   .left_counter_;
        cur_segm_counter -= segm_end_point_it->second   .right_counter_;
 
        if(
                segm_end_point_it   ==  segm_end_points.begin()
            ||  cur_segm_counter    >   max_segm_counter
          )
        {
            max_segm_counter = cur_segm_counter;
            T_segm_end_points::iterator  next_it = segm_end_point_it;
            std::advance(next_it, 1);
            max_segm_counter_point = (segm_end_point_it->first + next_it->first) / 2.0;
        }
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
void  input_segments(T_segments&  segments)
{
    int  segments_total = 0;
    do
    {
        std::cout << "Введите количесто заданных отрезков на прямой: ";
        
        std::cin >> segments_total;    
    }while(segments_total <= 0);
 
    std::cout << "Введите координаты "
              << segments_total
              << " отрезков в виде (1.2,3.4):"
              << std::endl;
 
    segments.resize(segments_total);
    for(int  i = 0; i < segments_total;)
    {        
        std::cout << "\t#"
                  << i + 1
                  << ": ";
        
        std::cin >> segments[i];
        if( segments[i].real() < segments[i].imag() )
        {
            ++i;
        }
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    T_segments  segments;
 
    input_segments(segments);
    
    int         max_segm_counter        = 0;
    T_coord     max_segm_counter_point  = 0;
 
    get_max_segm_counter_and_max_segm_counter_point
        (
            segments,
            max_segm_counter,
            max_segm_counter_point
        );
 
    std::cout << "Наибольшему количеству отрезков ("
              << max_segm_counter
              << ") принадлежит точка "
              << max_segm_counter_point
              << "."
              << std::endl;
}
0
4043 / 2332 / 292
Регистрация: 03.02.2011
Сообщений: 5,066
Записей в блоге: 10
12.01.2012, 16:05 16
Цитата Сообщение от slava0394 Посмотреть сообщение
жесть
Фигня Вот то, что Mr.X сваял, то - да, жесть, она самая. Сразу видно, что у человека до того рука набита, что на пальцах, наверно, уже мозоли от клавиатуры.
1
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
13.01.2012, 00:25 17
Цитата Сообщение от BRcr Посмотреть сообщение
Вот то, что Mr.X сваял, то - да, жесть
Действительно, два счетчика в мэпе - это жесть, можно использовать один:
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

/////////////////////////////////////////////////////////////////////////////////////////
//Дано множество отрезков на прямой. Найти точку, которая принадлежит наибольшему 
//количеству отрезков, определить это количество.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef double                                  T_coord;
typedef int                                     T_counter;
typedef std::complex    <T_coord>               T_segment;
typedef std::vector     <T_segment>             T_segments;
typedef std::map        <T_coord, T_counter>    T_segm_end_points;
typedef std::vector     <T_counter>             T_counters;
/////////////////////////////////////////////////////////////////////////////////////////
void  fill_segm_end_points
    (
        const T_segments&   segments,
        T_segm_end_points&  segm_end_points
    )
{
    for(
        T_segments::const_iterator  segm_it = segments.begin();
        segm_it != segments.end();
        ++segm_it
       )
    {
        ++segm_end_points[segm_it->real()];
        --segm_end_points[segm_it->imag()];
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
void  get_max_segm_counter_and_max_segm_counter_point
    (
        const T_segments&   segments,
        T_counter&          max_segm_counter,
        T_coord&            max_segm_counter_point    
    )
{
    T_segm_end_points  segm_end_points;
 
    fill_segm_end_points
        (
            segments,
            segm_end_points
        );
 
    struct  T_get_counter
    {
        T_counter  operator() (const T_segm_end_points::value_type&  segm_end_points_elem)
        {
            return  segm_end_points_elem.second;
        }
    };
 
    T_counters  counters;
    std::transform
        (
            segm_end_points.begin(),
            segm_end_points.end(),
            std::back_inserter(counters),
            T_get_counter()
        );
 
    T_counters  counters_sums;
    std::partial_sum
        (
            counters.begin(),
            counters.end(),
            std::back_inserter(counters_sums)
        );
    
    T_counters::iterator  max_sum_it  =     std::max_element
                                                (
                                                    counters_sums.begin(),
                                                    counters_sums.end()
                                                );
 
    max_segm_counter    = *max_sum_it;
 
    int  max_sum_dist   =   std::distance
                                (
                                    counters_sums.begin(),
                                    max_sum_it
                                );
 
    T_segm_end_points::const_iterator  L = segm_end_points.begin();
    std::advance(L, max_sum_dist);
    T_segm_end_points::const_iterator  R = L;
    std::advance(L, 1);
 
    max_segm_counter_point = (L->first + R->first) / 2.0;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  input_segments(T_segments&  segments)
{
    int  segments_total = 0;
    do
    {
        std::cout << "Введите количесто заданных отрезков на прямой: ";
        
        std::cin >> segments_total;    
    }while(segments_total <= 0);
 
    std::cout << "Введите координаты "
              << segments_total
              << " отрезков в виде (1.2,3.4):"
              << std::endl;
 
    segments.resize(segments_total);
    for(int  i = 0; i < segments_total;)
    {        
        std::cout << "\t#"
                  << i + 1
                  << ": ";
        
        std::cin >> segments[i];
        if( segments[i].real() < segments[i].imag() )
        {
            ++i;
        }
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    T_segments  segments;
 
    input_segments(segments);
    
    T_counter   max_segm_counter        = 0;
    T_coord     max_segm_counter_point  = 0;
 
    get_max_segm_counter_and_max_segm_counter_point
        (
            segments,
            max_segm_counter,
            max_segm_counter_point
        );
 
    std::cout << "Наибольшему количеству отрезков ("
              << max_segm_counter
              << ") принадлежит точка "
              << max_segm_counter_point
              << "."
              << std::endl;
}
1
1 / 1 / 1
Регистрация: 05.12.2011
Сообщений: 39
13.01.2012, 11:49  [ТС] 18
нифига себе) она работает?
0
13.01.2012, 11:49
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 13.01.2012, 11:49
Помогаю со студенческими работами здесь

Сгенерировать случайную точку, принадлежащую полигонув map area
Задание: сгенерировать случайную точку, которая бы лежала внутри полигона area с заданными...

Найти точку координат на окружности имея начальную точку и расстояние
Здравствуйте. Есть точка с известными координатами A(a, b, c) и есть точка с неизвестными...

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

Как вызвать функцию принадлежащую классу?
Есть функция: void __fastcall CVolumeOutWave::SetCurrentVolume( DWORD dwValue ) Когда пытаюсь ее...


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru