Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Pascal] Множества 
V
    Опции темы
InviZible
Дата 11.11.2006, 16:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 63
Регистрация: 13.9.2006

Репутация: нет
Всего: нет
Даны 2 множества точек(берутся из 2-х текстовиков) на плоскости. Выбрать 4-те точки первого множества так, чтобы квадрат с вершинами в этих точках накрывал все точки второго множества и 

имел минимальную площадь.

я понял так:
1 считываем в массивы координаты точек
2 проверяем получился ли квадрат из 1-го множ-ва
3 проверяем, накрывает ли крвадрат точки 2-го множ-ва
4 если да, то смотрим минимальна ли его площадь
5 потом всё рисуем на экране.

правильно алгоритм составил? 
как осуществить пункт 2 и 3?
PM MAIL   Вверх
anwe
Дата 11.11.2006, 19:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 748
Регистрация: 2.9.2006

Репутация: 9
Всего: 23
Да, алгоритм правильный.
По пункту 2.
Пусть есть точки А, В, С и Д
1. Надо проверить на параллельность две противоположные стороны: АВ и СД, после ВС и ДА.
2. Надо проверить две противоположные стороны на их равенство: АВ и СД; ВС и ДА.
3. Надо проверить перепендикулярность двух соседних отрезков, допустим АВ и ВС.
По пункту 3.
На пересечении диагоналей квадрата находишь точку центра квадрата. От нее рисуешь (находишь уравнения) прямые через точку второго множества. Находишь точки пересечения этой прямой со сторонами квадрата. Если искомая точка второго множества находится внутри точек пересечения этой прямой и сторон квадрата, значит она не принадлежит квадрату.
PM MAIL   Вверх
Kuvaldis
Дата 11.11.2006, 20:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
anwe, 
Цитата

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

ИМХО, проще и красивее можно сделать.  Используем понятие колебания. Любая прямая на плоскости разбивает плоскость на две полуплоскости: положительную и отрицательную. Т.е. если подставить координаты любой из точек в положительной полуплоскости в уравнение прямой, то это число будет положительное, аналогично и для отрицательной полуплоскости.
ВОт из этого и исходим.
Уравнения сторон квадрата будут уже найдены в предыдущих пунктах (при проверке на квадрат).
Если взять произвольную точку внутри квадрата (например, как ты предложил, пересечение диагоналей), то и для ВСЕХ точек внутри квадрата колебаний относительно всех четырех  сторон будет одинаковое. Эти значения нужно сохранить.
А потом перебирать все точки из второго множества и проверять, что колебания относительно соответствующих прямых совпадают.
ЭТо НАМНОГО проще, особенно если 2 множество достаточно большое.

InviZible, 
я что-то не совсем понял, а количество точек, по которым строить квадрат, какое? Если их много, то тебе придется еще и эффективный алгоритм генерации сочетаний из N элементов по 4 искать.


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
InviZible
Дата 11.11.2006, 21:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 63
Регистрация: 13.9.2006

Репутация: нет
Всего: нет
Kuvaldis, да, точек в файле много, нужно выбрать такие что б квадрат покрывал 2е множество и имел миним-ю площадь. Если у тебя есть хороший алгоритм, то пожалуйста выложи здесь.
PM MAIL   Вверх
anwe
Дата 11.11.2006, 21:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 748
Регистрация: 2.9.2006

Репутация: 9
Всего: 23
Kuvaldis, ты написал:
Цитата
Т.е. если подставить координаты любой из точек в положительной полуплоскости в уравнение прямой, то это число будет положительное, аналогично и для отрицательной полуплоскости

Как подставить? Точки же плоскости не принадлежат прямой. И прямая разбивает плоскость, значит точки на ней не принадлежат ни одной полуплоскости.
И вообще, как я понял, значит надо проверять точки для всех четырех сторон. Во-первых, это тоже не мало, а еще надо решать задачу принадлежности точки плоскости. Во-вторых, принадлежность положительной или отрицательной полуплоскости зависит от того, как решающий условится их (полуплоскости) определять.

А если точек много, можно их быстро отсеять так: если точки лежат внутри вписанной в квадрат окружности (расстояние от центра квадрата до точки меньше половины длины стороны квадрата) - то принадлежит квадрату однозначно; если вне описанной окружности (расстояние больше, чем половина корня из двух, умноженного на длину стороны квадрата) - точка однозначно не принадлежит; и если больше вписанного и меньше описанного - надо проверять.
PM MAIL   Вверх
Kuvaldis
Дата 11.11.2006, 22:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
anwe, 
Цитата

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

Рассмотрим прямую y = x, в каноническом виде y - x = 0
если подставим координаты любой точки, то для ВСЕХ точек над прямой y - x > 0
для ВСЕХ точек под прямой  y - x < 0
Для ВСЕХ точек на прямой y - x = 0
Это вообще аналитическая геометрия 1 курс.

Нарисуй произвольные 4 прямые и возьми точку внутри и для всех точек плоскости разбей полуплоскости на + и -. т.е. сверху +, снизу -  для каждой прямой
итого для каждой области будут свои + и -. Если взять произвольную точку внутри фигуры, то для нее будет однозначная комбинация + и - для каждой прямой.
Соответственно, подставляя произвольную точку внутри фигуры, мы можем определить ее смещения....
ну вроде понятно...

Цитата

. Во-вторых, принадлежность положительной или отрицательной полуплоскости зависит от того, как решающий условится их (полуплоскости) определять.

Определяем знак по точке, которая ТОЧНО лежит внутри, т.е. пересечение диагоналей

Это сообщение отредактировал(а) Kuvaldis - 11.11.2006, 22:36


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
Aloha
Дата 11.11.2006, 23:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


.
**


Профиль
Группа: Участник Клуба
Сообщений: 351
Регистрация: 14.5.2006

Репутация: 97
Всего: 165
InviZible

Присоединённый файл ( Кол-во скачиваний: 23 )
Присоединённый файл  01.rar 37,41 Kb
PM   Вверх
anwe
Дата 11.11.2006, 23:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 748
Регистрация: 2.9.2006

Репутация: 9
Всего: 23
Цитата(Kuvaldis @ 11.11.2006,  21:16)
Это вообще аналитическая геометрия 1 курс.

А, может, незачем делать такие укоры: я филолог по образованию.
PM MAIL   Вверх
Kuvaldis
Дата 12.11.2006, 00:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
anwe, 
Цитата

А, может, незачем делать такие укоры: я филолог по образованию.

Извини, плиз, если я тебя обидел или задел. Я просто хотел сказать, откуда это все взялось и в каком направлении смотреть... smile 

Aloha, 
я снимаю перед тобой шляпу, ты монстр. Уже не в первый раз твой пост - это маленький шедевр!!!
+ без вариантов!!! smile 

Это сообщение отредактировал(а) Kuvaldis - 12.11.2006, 00:42


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
InviZible
Дата 12.11.2006, 00:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 63
Регистрация: 13.9.2006

Репутация: нет
Всего: нет
Kuvaldis, спасибо за советы и файл, буду разбираться.
PM MAIL   Вверх
InviZible
Дата 17.11.2006, 20:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 63
Регистрация: 13.9.2006

Репутация: нет
Всего: нет
Что-то не получается с квадратом. 
Я перебираю все координаты, ищу стороны a,b,c,d . Затем скалярное произведение, чтобы узнать перпендикулярны ли стороны, елси да, и a=b=c=d, то точки составляют квадрат. Но что-то он мне ничего не выдаёт путного. Вот код:
Код

program lr5_19;
uses crt,graph;
var
 x1,y1,x2,y2:array[1..50] of real;
 gm,gd,kk,k,q,s,j,i,n:integer;
 f1,f2:text;
 a,b,c,d:real;
begin
 clrscr;
 {-----------------------start 1 set--------------}
 writeln('****** 1 set ******');
 assign(f1,'E:\tp7\bin\test\t1.txt');
 reset(f1);
 i:=1;
 while not eof(f1) do
  begin
   readln(f1,x1[i],y1[i]);
   writeln(x1[i]:6:2,' ',y1[i]:6:2);
   inc(i);
  end;
 n:=i-1;
{-------------------------------------- end of 1 set-----}
writeln(n,' = kol-vo tochek ');
{-------------------------------------- start of 2 set---}
writeln('****** 2 set ******');
 assign(f2,'E:\tp7\bin\test\t2.txt');
 reset(f2);
 i:=1;
 while not eof(f2) do
  begin
   readln(f2,x2[i],y2[i]);
   writeln(x2[i]:6:2,' ',y2[i]:6:2);
   inc(i);
  end;
 {-------------------------------------- end of 2 set-----} 
 kk:=0;
 for j:=1 to n do
  for k:=1 to n do
   for q:=1 to n do
    for s:=1 to n do
     begin
      {nahodim dlini storon}
      a:=sqrt(sqr(x1[k]-x1[j])+sqr(y1[k]-y1[j]));
      b:=sqrt(sqr(x1[q]-x1[k])+sqr(y1[q]-y1[k]));
      c:=sqrt(sqr(x1[s]-x1[q])+sqr(y1[s]-y1[q]));
      d:=sqrt(sqr(x1[j]-x1[s])+sqr(y1[j]-y1[s]));
      {skalyar proizved}
     if ((x1[j]*x1[k]+y1[j]*y1[k])=0) and ((x1[k]*x1[q]+y1[k]*y1[q])=0)
      and ((x1[q]*x1[s]+y1[q]*y1[s])=0) and ((x1[s]*x1[j]+y1[s]*y1[j])=0) then
      begin
       if (a=b) and (a=c) and (a=d) and (b=c) and (b=d)
        and (c=d) and (a<>0) and (b<>0) and (c<>0) and (d<>0) then
         begin
        writeln('=======================');
        writeln('a      b      c      d');
        writeln(a:6:2,' ',b:6:2,' ',c:6:2,' ',d:6:2);
        writeln('  j      k      q      s     ');
        writeln('x ',x1[j]:6:2,' ',x1[k]:6:2,' ',x1[q]:6:2,' ',x1[s]:6:2);
        writeln('y ',y1[j]:6:2,' ',y1[k]:6:2,' ',y1[q]:6:2,' ',y1[s]:6:2);
        inc(kk);
         end;
      end;
    end;
  writeln('Naideno kvadratov : ', kk);
  readln;

end.


Это сообщение отредактировал(а) InviZible - 17.11.2006, 20:27
PM MAIL   Вверх
anwe
Дата 18.11.2006, 01:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 748
Регистрация: 2.9.2006

Репутация: 9
Всего: 23
InviZible, по-моему ты смешал два понятия. В строках
Код

      a:=sqrt(sqr(x1[k]-x1[j])+sqr(y1[k]-y1[j]));
      b:=sqrt(sqr(x1[q]-x1[k])+sqr(y1[q]-y1[k]));
      c:=sqrt(sqr(x1[s]-x1[q])+sqr(y1[s]-y1[q]));
      d:=sqrt(sqr(x1[j]-x1[s])+sqr(y1[j]-y1[s]));
ты рассматриваешь x1[] y1[] как точки. А дальше находишь
Цитата
скалярное произведение
и строка
Код

 if ((x1[j]*x1[k]+y1[j]*y1[k])=0) and ((x1[k]*x1[q]+y1[k]*y1[q])=0)
      and ((x1[q]*x1[s]+y1[q]*y1[s])=0) and ((x1[s]*x1[j]+y1[s]*y1[j])=0) then
справедлива для векторов. А в векторах x1 и y1 это не координата.
К тому же, для векторов получается x1[j];y1[j] - компоненты первого вектора, x1[k];y1[k] - второго. Получается всего в этой строке проверяешь на перпендикулярность 8 векторов.
PM MAIL   Вверх
InviZible
Дата 18.11.2006, 20:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 63
Регистрация: 13.9.2006

Репутация: нет
Всего: нет
А что нужно исправить? что-то не понятно =(
PM MAIL   Вверх
anwe
Дата 19.11.2006, 03:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 748
Регистрация: 2.9.2006

Репутация: 9
Всего: 23
Проще воспользоваться следующим условием. Пусть есть 4 точки (х1,у1), (х2,у2), (х3,у3), (х4,у4). Тогда берешь отрезки попарно и проверяешь их на параллельность. Они параллельны, если условие (y2-y1)/(x2-x1)=(y4-y3)/(x4-x3) истина. Далее другая пара: (y3-y2)/(x3-x2)=(y4-y1)/(x4-x1). Далее по теореме какой-то, да и просто по логике, на перпендикулярность надо проверить лишь два соседних отрезка. Если они перпендикулярны, то другие два соседних также перпендикулярны. Условие перепендикулярности: (y2-y1)/(x2-x1)=-(x3-x2)/(y3-y2).
PM MAIL   Вверх
InviZible
Дата 19.11.2006, 13:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 63
Регистрация: 13.9.2006

Репутация: нет
Всего: нет
С квадратом вчера разобрался: проверяю равенство сторон и равенство диагоналей. Теперь осталось проверка на вхождение точек второго мно-ва в квадрат, почти сделал: беру расстояний от точки до 2х противоподожных вершин если меньше стороны, то - входит. Осталось с площадями разобраться...и нарисовать
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0648 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.