Помощь - Поиск - Пользователи - Календарь
Полная версия: Отрезки имеющие общие точки
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Рустам
Даны действительные числа a1..a50 эти числа определяют 25 интервалов числовой оси
(a1,a2) , (a3,a4) и тд.
имеют ли все данные интервалы общие точки, если да то указать какую нибудь из этих точек



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

uses crt;
const n=4; {для примера рассматривал 4 интервала только}
var
a: array[1..2,1..n] of integer;
i,j,k:  integer;

b: array [1..2] of integer;
begin
clrscr;

for i:=1 to n do    begin
writeln('x,y');
for j:=1 to 2 do   begin

readln(a[i,j])
end;
end;


for i:=1 to n do begin

for j:=1 to 2 do begin
write(a[i,j]:3);
end;
writeln;
end;

{раз все интервалы могут иметь общую точку то достаточно взять один интервал первый например и сравнить со всеми}
for i:=2 to n do
begin
if (a[1,1]<a[i,1]) and (a[1,2]<a[i,2]) and (a[1,2]>a[i,1])  {если первый лежит чуть левее}
then
begin
b[1]:=a[i,1]; b[2]:=a[1,2];

if (a[1,1]>a[i,1]) and (a[1,2]>a[i,2]) and (a[i,1]<a[i,2]){если первый интервал лежит чуть правее}
then
begin
if b[2]<a[i,2] then b[2]:=a[i,2];
if b[1]<a[1,1] then b[1]:=a[1,1];
end;

if  (a[1,1]<a[i,1]) and (a[2,2]>a[i,2]) then  begin {если первый интервал содержит следующий}
b[1]:=a[i,1]; 
b[2]:=a[i,2];
end;

if (a[1,1]>a[i,1]) and (a[2,2]<a[i,2]) then begin {если первый интервал содержится в следующем}
b[1]:=a[1,1];
b[2]:=a[2,2];
end;
end;

readkey;
end.

volvo
А если без такого количества сравнений? Просто взять, первый интервал запомнить как общий интервал (очевидно, что если есть общая точка, то она должна принадлежать и первому интервалу, правда?), а начиная со второго - смотреть: если начало очередного интервала (назовем его A[ i ]) лежит правее начала общего - то новым началом общего интервала станет точка A[ i ]. Если конец нового интервала (назовем его A[j]) левее конца общего - то новым концом общего интервала станет A[j]... В конце - проверить, если начало общего интервала лежит правее конца, то общие точки есть, и взять любую из них. Если же начало левее конца - то общих точек нет...

Это все - на правах догадки... Хотя, по-моему, должно сработать...

Вкралась ошибка, выделенное красным слово раньше было "правее"
Рустам
Я тебя почти понял)) спасибо завтра попробую smile.gif
passat
Если не ошибся с пониманием, то у Вас типовая задача на связность областей.
Решается обычно приблизительно так:
1. Заводится массив из N структур(записей) данных (или 2 массива размерностью по N), где ключом являются координаты Ваших точек. Началу отрезка присваивается +1, концу -1.
2. Массив сортируется по ключу.
3. Идем по массиву и считаем сумму +1 и -1.
4. Если сумма достигла 25, то общей точкой будет ключ этой точки.
5. Дополнительно надо проверить не пересекаются ли все отрезки по границе.

Если известно, что заданные числа только целые, то имеет смысл преобразовать их к вещественным и добавить к конечным точкам дробную часть. Так Вы избавитесь от проверки пересечения на границе.
passat
Опять же если правильно понял условие, то задачу можно решить за один проход по последовательности. (Это решение вытекает из предыдущего).
1.Считываем числа попарно (начало/конец).
2.Среди первой последовательности ищем максимум, а среди второй минимум.
3а.Если максимум не больше минимума, то выводим любое число из полученного интервала.
3б.Если нет, то ВСЕ отрезки не имеют ни одной общей точки. Т.е. хотя бы один отрезок заканчивается раньше чем открывается хотя бы один другой.
volvo
То есть, мой вариант, который делает то же самое (за один проход, естественно, а ты думал что, я буду проходить 15 раз туда-сюда?), ты предпочел НЕ заметить, и теперь двигаешь "революционную" идею, да? Мудро... Далеко пойдешь...
passat
Цитата(volvo @ 28.05.2009 15:58) *

То есть, мой вариант, который делает то же самое (за один проход, естественно, а ты думал что, я буду проходить 15 раз туда-сюда?), ты предпочел НЕ заметить, и теперь двигаешь "революционную" идею, да?

Я ничего, никого и никуда не двигаю. Нужно это человеку или нет - не знаю.
Угодно стереть - стирайте. Не вопрос ни разу.

Цитата

Мудро... Далеко пойдешь...

Спасибо. Я уже пришел.

Пальма первенства за Вами.
Lapp
Цитата(passat @ 28.05.2009 17:16) *
Я ничего, никого и никуда не двигаю. Нужно это человеку или нет - не знаю.
Угодно стереть - стирайте. Не вопрос ни разу.
Спасибо. Я уже пришел.

Пальма первенства за Вами.
passat, нет никакой нужды кипятится. Если ты отвечаешь в тему - пожалуйста, дай себе труд прочитать все сообщения в ней. Это не только тут, это на всех форумах, и не только на форумах. Включаешься в разговор - сначала прислушайся к нему. Назови это первенством, этикетом, вежливостью - как хочешь.
Если я попадал в подобную ситуацию (со мной бывало) - я извинялся. Прийми это как совет. Не вижу смысла оскорбляться..
Рустам
Спасибо всем)) если как нить поможет могу свою прогу выложить.. рабочая она + там ещё одну вещь делает
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.