Форум программистов, компьютерный форум, киберфорум
Наши страницы

Pascal ABC

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
eXPonent
99 / 52 / 2
Регистрация: 21.05.2012
Сообщений: 1,170
#1

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

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

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

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

Это всё что я смог раздобыть в интернете.
Опыт в программировании у меня есть, но тут не понимаю даже как сделать
Язык можно Pascal (любой, но лучше ABC) или Delphi (я думаю я его смогу перевести в Pascal ABC)
Пожалуйста помогите...
Заранее благодарен
0
Вложения
Тип файла: rar Задача.rar (4.1 Кб, 11 просмотров)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.05.2012, 14:21
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найти точку, которая принадлежит наибольшему количеству отрезков (Pascal ABC):

Ввести количество отрезков и их длины; найти, сколько треугольников можно составить из этих отрезков - Pascal ABC
надо написать такую программу: пользователь вводит количество отрезков и их длины, и надо найти сколько треугольников можно составить из...

Проверить, принадлежит ли точка одному из отрезков (2, 5) и [6,5, 19). Координата точки вводится пользователем - Pascal ABC
13.Составить алгоритм и написать решение задачи на Паскале: Проверить, принадлежит ли точка одному из отрезков (2, 5) и [6,5, 19)....

Определить, принадлежит ли данная точка одному из отрезков, обоим или лежит вне их - Pascal ABC
Даны отрезки и и точка A с координатой х. Определить, принадлежит ли данная точка одному из этих отрезков, обоим или лежит вне их

Найти из множества материальных точку, которая наиболее близко расположена к центру тяжести этого множества - Pascal ABC
В трехмерном пространстве задано множество материальных точек. Найти ту из них, которая наиболее близко расположена к центру тяжести этого...

Составит программу,которая по введенному количеству лет определяет возрастную категорию - Pascal ABC
3.Составит программу,которая по введенному количеству лет определяет следующую возрастную...

Составить программу , которая проверяет, можно ли из отрезков построить четырёхугольник - Pascal
Помогите плз! Составить программу , которая проверяет , можно ли из отрезков a,b,c,d построить четырёх угольник!!!!!!

23
valeriikozlov
Эксперт С++
4682 / 2508 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
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
eXPonent
99 / 52 / 2
Регистрация: 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
valeriikozlov
Эксперт С++
4682 / 2508 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
22.05.2012, 21:18 #4
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
Отрезок от 19 до 20, или я ошибаюсь?
вообще-то вопрос стоял:
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
Найти точку, принадлежащую наибольшему количеству отрезков.
а не отрезок.
Т.е. нужно вывести любую точку, попадающую под ответ.
Вообще в этой задаче может быть полным ответом: точка или точки, или отрезок или отрезки.
Но нужно вывести только одну точку. Если под ответ попадает несколько точек, то обычно подразумевается, что вывести любую из них.
1
eXPonent
99 / 52 / 2
Регистрация: 21.05.2012
Сообщений: 1,170
22.05.2012, 21:34  [ТС] #5
Спасибо Валера, а как можно изменить мой или твой алгоритм, что бы можно было выводить несколько отрезков или несколько точек?
0
valeriikozlov
Эксперт С++
4682 / 2508 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
22.05.2012, 21:39 #6
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
Спасибо Валера, а как можно изменить мой или твой алгоритм, что бы можно было выводить несколько отрезков или несколько точек?
можно, расскажу как это сделать (или даже напишу изменения в код), но сначало Вы мне расскажите, зачем Вам это нужно. (я просто встречал эту задачу - она олимпиадная, и нужно было просто вывести кординату одной точки)
1
eXPonent
99 / 52 / 2
Регистрация: 21.05.2012
Сообщений: 1,170
22.05.2012, 21:47  [ТС] #7
Мне эту задачу задал учитель по информатике.
Валера, а мой код вам понятен?
0
valeriikozlov
Эксперт С++
4682 / 2508 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
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
eXPonent
99 / 52 / 2
Регистрация: 21.05.2012
Сообщений: 1,170
23.05.2012, 11:18  [ТС] #9
Валера, а если пара точек это числа дробные, то как быть?
0
Puporev
Модератор
54020 / 41653 / 14732
Регистрация: 18.05.2008
Сообщений: 97,927
23.05.2012, 11:25 #10
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
а если пара точек это числа дробные,
Да какая разница? Точка принадлежит отрезку, если
ai<=x<=bi и какая разница целое число или вещественное.
0
valeriikozlov
Эксперт С++
4682 / 2508 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
23.05.2012, 11:29 #11
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
а если пара точек это числа дробные, то как быть?
Предыдущий код расчитан только на ввод целых чисел. Если работать с числами типа real, то такой алгоритм вообще не подходит.
1
Puporev
Модератор
54020 / 41653 / 14732
Регистрация: 18.05.2008
Сообщений: 97,927
23.05.2012, 11:32 #12
Вообще условие задачи или не полное, или идиотское. При таких исходных данных искомая точка может иметь только целую координату, иначе бесконечное число решений.
Я сначала невнимательно прочитал условие и подумал что даны точки и отрезки.
0
eXPonent
99 / 52 / 2
Регистрация: 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
eXPonent
99 / 52 / 2
Регистрация: 21.05.2012
Сообщений: 1,170
23.05.2012, 11:46  [ТС] #14
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Предыдущий код расчитан только на ввод целых чисел. Если работать с числами типа real, то такой алгоритм вообще не подходит.
А можно его каким-то образом модифицировать?
0
Puporev
Модератор
54020 / 41653 / 14732
Регистрация: 18.05.2008
Сообщений: 97,927
23.05.2012, 11:53 #15
Цитата Сообщение от ARTYRXOX Посмотреть сообщение
А можно его каким-то образом модифицировать?
Задача решается только для целых, иначе ответь на вопрос сколько точек лежит на отрезке [0;1]?
0
23.05.2012, 11:53
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2012, 11:53
Привет! Вот еще темы с ответами:

Создайте программу, которая запрашивает длины двух отрезков и выводит на экран эти отрезки - Pascal ABC
Создайте программу, которая запрашивает длины двух отрезков и выводит на экран эти отрезки ( в масштабе 1 ед.=5 пикселей) и их &quot;общую меру&quot;...

Даны длины трех отрезков. Определить, можно ли из этих отрезков сложить треугольник? - Pascal
Даны длины трех отрезков. Определить, можно ли из этих отрезков сложить треугольник? и как сделать схему данной программы???

Даны длины трех отрезков. Определить, можно ли из этих отрезков сложить треугольник - Pascal
помогите ещё одну задачу)

Даны длины трех отрезков. Проверить, можно ли из заданных отрезков построить прямоугольный треугольник. - Pascal ABC
Даны длины трех отрезков. Проверить, можно ли из заданных отрезков построить прямоугольный треугольник. Входные данные: Во входном...


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

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

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