99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
1

Найти точку, которая принадлежит наибольшему количеству отрезков

21.05.2012, 14:21. Показов 4051. Ответов 23
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Дано N отрезков на прямой. Найти точку, принадлежащую наибольшему количеству отрезков. Отрезок задается парой точек Ai < Bi.
Ограничения : 1 <=N<=10000, -1000<= Аi <= Bi <= 1000.
Формат ввода: В первой строке вводится число N. В следующих N строках вводятся пары чисел Ai и Bi.
Формат вывода: вывести X - координату искомой точки.

Похожая задача решена, но она сделана на С++ от Mr.X
найти точку, принадлежащую
Я там ничего не понял так как вообще незнаком с С++
Я прикрепил файл Задача.rar там указаны похожие задачи и методы их решения

Это всё что я смог раздобыть в интернете.
Опыт в программировании у меня есть, но тут не понимаю даже как сделать
Язык можно Pascal (любой, но лучше ABC) или Delphi (я думаю я его смогу перевести в Pascal ABC)
Пожалуйста помогите...
Заранее благодарен
Вложения
Тип файла: rar Задача.rar (4.1 Кб, 12 просмотров)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.05.2012, 14:21
Ответы с готовыми решениями:

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

Среди точек первого множества найти такую,которая принадлежит наибольшему количеству множеств.
Мне нужно написать эту программу,я совершенно не знаю как это сделать.Знаю только,что пишется она с...

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

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

23
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
22.05.2012, 07:44 2
проверяйте:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var
i,n,x,a,b,tmp,col, m:longint;
mas:array[-1000..1000,1..2] of longint;
begin
read(n);
for i:=1 to n do begin
read(a,b);
inc(mas[a,1]);
inc(mas[b,2]);
end;
for i:=-1000 to 1000 do begin
if i=-8 then
inc(m);
inc(tmp,mas[i,1]);
if tmp>col then begin
x:=i;
tmp:=col;
end;
dec(tmp,mas[i,2]);
end;
write(x);
end.
1
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
22.05.2012, 16:21  [ТС] 3
Валера большое спасибо Вы натолкнули меня на мысль!
Я тестировал ваш алгоритм вот таким образом:
Ввод:2 10 20 20 30
Вывод:20
Ввод:2 10 20 19 30
Вывод:19
Ввод:3 10 20 18 30 19 20
Вывод:19
Это всё хорошо, но ведь во втором и третьем тесте, мне кажется должен быть ответ: Отрезок от 19 до 20, или я ошибаюсь?

Как я понял задачу:
На прямой строится N линий, найти точку наибольшего количества их пересечений.
Но ведь если первая прямая 1-20, а вторая 19-30, то наибольшее количество их пересечений будет отрезок от 19 до 20 или я не прав?

Вот какой код придумал я:
Pascal
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
Var mas:array[-1000..1000] of integer;
    a,b,max,i,j,N,X:integer;
 
BEGIN
 
Read(N);
For i:=1 to N do
 Begin
   a:=-1000;
   b:=1000;
   For j:=a to b do inc(mas[j]);
 End;
 
max:=-1;
For i:=-1000 to 1000 do
 Begin
   If max=mas[i] then inc(j);
   If max<mas[i] then
    Begin
      max:=mas[i];
      X:=i;
      j:=0;
    End;
 End;
 
If j<>0 then Writeln('Отрезок от ',X,' до ',X+j)
 else Writeln('Точка ',X);
Writeln;
 
END.
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
22.05.2012, 21:18 4
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
Отрезок от 19 до 20, или я ошибаюсь?
вообще-то вопрос стоял:
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
Найти точку, принадлежащую наибольшему количеству отрезков.
а не отрезок.
Т.е. нужно вывести любую точку, попадающую под ответ.
Вообще в этой задаче может быть полным ответом: точка или точки, или отрезок или отрезки.
Но нужно вывести только одну точку. Если под ответ попадает несколько точек, то обычно подразумевается, что вывести любую из них.
1
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
22.05.2012, 21:34  [ТС] 5
Спасибо Валера, а как можно изменить мой или твой алгоритм, что бы можно было выводить несколько отрезков или несколько точек?
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
22.05.2012, 21:39 6
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
Спасибо Валера, а как можно изменить мой или твой алгоритм, что бы можно было выводить несколько отрезков или несколько точек?
можно, расскажу как это сделать (или даже напишу изменения в код), но сначало Вы мне расскажите, зачем Вам это нужно. (я просто встречал эту задачу - она олимпиадная, и нужно было просто вывести кординату одной точки)
1
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
22.05.2012, 21:47  [ТС] 7
Мне эту задачу задал учитель по информатике.
Валера, а мой код вам понятен?
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
23.05.2012, 05:57 8
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
Валера, а мой код вам понятен?
да, мне понятен. Попробуйте для своего кода ввести 2 1 4 7 10.
Или так: 3 1 4 3 6 6 9
Лучше тогда так сделать:
Pascal
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
var
i,n,a,b,tmp,col,max:longint;
mas:array[-1000..1000,1..2] of longint;
begin
read(n);
for i:=1 to n do begin
read(a,b);
inc(mas[a,1]);
inc(mas[b,2]);
end;
for i:=-1000 to 1000 do begin
inc(col,mas[i,1]);
if max<col then 
max:=col;
dec(col,mas[i,2]);
end;
col:=0;
for i:=-1000 to 1000 do begin
inc(col,mas[i,1]);
if (max=col) then begin
if tmp=0 then tmp:=i;
if mas[i,2]<>0 then begin
if tmp=i then writeln('Точка ', i) else
writeln('Отрезок ', tmp,' ', i);
tmp:=0;
end;
end else tmp:=0; 
dec(col,mas[i,2]);
end; 
 
end.
1
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
23.05.2012, 11:18  [ТС] 9
Валера, а если пара точек это числа дробные, то как быть?
0
Почетный модератор
64299 / 47594 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
23.05.2012, 11:25 10
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
а если пара точек это числа дробные,
Да какая разница? Точка принадлежит отрезку, если
ai<=x<=bi и какая разница целое число или вещественное.
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
23.05.2012, 11:29 11
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
а если пара точек это числа дробные, то как быть?
Предыдущий код расчитан только на ввод целых чисел. Если работать с числами типа real, то такой алгоритм вообще не подходит.
1
Почетный модератор
64299 / 47594 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
23.05.2012, 11:32 12
Вообще условие задачи или не полное, или идиотское. При таких исходных данных искомая точка может иметь только целую координату, иначе бесконечное число решений.
Я сначала невнимательно прочитал условие и подумал что даны точки и отрезки.
0
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
23.05.2012, 11:32  [ТС] 13
Интересно, а если даны такие значения:
2 2 3,14 3,14 4
Она разве выдаст точку 3,14?
Она ведь завершится с ошибкой!
Pascal
1
2
3
4
5
6
7
8
9
10
var
i,n,a,b,tmp,col,max:[B]longint[/B];
mas:array[-1000..1000,1..2] of [B]longint[/B];
begin
read(n);
for i:=1 to n do begin
[B]read(a,b);[/B]
inc(mas[a,1]);
inc(mas[b,2]);
end;
0
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
23.05.2012, 11:46  [ТС] 14
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Предыдущий код расчитан только на ввод целых чисел. Если работать с числами типа real, то такой алгоритм вообще не подходит.
А можно его каким-то образом модифицировать?
0
Почетный модератор
64299 / 47594 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
23.05.2012, 11:53 15
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
А можно его каким-то образом модифицировать?
Задача решается только для целых, иначе ответь на вопрос сколько точек лежит на отрезке [0;1]?
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
23.05.2012, 11:58 16
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
А можно его каким-то образом модифицировать?
этот алгоритм нельзя модифицировать под работу с числами real. Нужен абсолютно другой алгоритм.
1
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
23.05.2012, 12:03  [ТС] 17
Цитата Сообщение от valeriikozlov
этот алгоритм нельзя модифицировать под работу с числами real. Нужен абсолютно другой алгоритм.
А его тяжело будет придумать?
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
23.05.2012, 12:12 18
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
А его тяжело будет придумать?
к сожалению невозможно.

Ладно, посмотрим, что-нибудь придумаю - только работать другой код будет намного медленнее.
1
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
23.05.2012, 12:25  [ТС] 19
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Ладно, посмотрим, что-нибудь придумаю - только работать другой код будет намного медленнее.
Ничего, большое спасибо за всё!
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
23.05.2012, 13:22 20
Pascal
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
var
i,n,N_a,j,i_min, col, max, tmp1:longint;
mas:array[1..20000,1..2] of longint;
mas1:array[1..20000] of real;
mas2:array[1..10000,1..2] of real;
tmp:real;
fl1, fl2:boolean;
begin
N_a:=1;
read(n);
for i:=1 to n do begin
read(mas2[i,1],mas2[i,2]);
fl1:=true; fl2:=true;
for j:=1 to i-1 do begin
if mas1[j]=mas2[i,1] then fl1:=false;
if mas1[j]=mas2[i,2] then fl2:=false;
end;
if fl1=true then begin
mas1[N_a]:=mas2[i,1]; inc(N_a);
end;
if fl2=true then begin
mas1[N_a]:=mas2[i,2]; inc(N_a);
end;
end;
 
for i:=1 to N_a do begin
i_min:=i;
for j:=i+1 to N_a do 
if mas1[i_min]>mas1[j] then i_min:=j;
tmp:=mas1[i]; mas1[i]:=mas1[i_min]; mas1[i_min]:=tmp;
end;
 
for i:=1 to n do begin
for j:=1 to N_a do 
if mas1[j]=mas2[i,1] then begin
inc(mas[j,1]); break;
end;
for j:=1 to N_a do 
if mas1[j]=mas2[i,2] then begin
inc(mas[j,2]); break;
end;
end;
 
for i:=1 to N_a do begin
inc(col,mas[i,1]);
if max<col then 
max:=col;
dec(col,mas[i,2]);
end;
 
col:=0;
for i:=1 to N_a do begin
inc(col,mas[i,1]);
if (max=col) then begin
if tmp1=0 then tmp1:=i;
if mas[i,2]<>0 then begin
if tmp1=i then writeln('Точка ', mas1[i]) else
writeln('Отрезок ', mas1[tmp1],' ', mas1[i]);
tmp1:=0;
end;
end else tmp1:=0; 
dec(col,mas[i,2]);
end; 
 
end.
1
23.05.2012, 13:22
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.05.2012, 13:22
Помогаю со студенческими работами здесь

Найти элемент строки, принадлежащий наибольшему количеству столбцов
моя цель )) наити элемент строки принадлежащий наибольшему количеству столбцов правильно ли...

Существует целочисленная точка, принадлежащая наибольшему количеству Z интервалов. Найти Z
Здравствуйте, уважаемые форумчане. Помогите придумать БЫСТРЫЙ алгоритм к следующей задаче. На...

Найти точку пересечения двух отрезков
как найти точку пересечения двух отрезков, если даны координаты начала и конца обеих

Найти точку пересечения отрезков в трехмерном пространстве
Как найти точку пересечения отрезков(если пересекаются) в трехмерном пространстве, если известны...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru