VPF::Массивы - Форум программистов

kura1

Дата 14.11.2008, 02:32 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: нет

Привет!

задачка-головоломка
smile

не могу понять алгоритм решения

Код


даны 2 множества точек на плоскости.из 1 множества выбрать 3 различных точки так, чтобы треугольник с вершинами в  этих точках содержал (строго в нутри себя) равное количество точек 1-го и 2-го множеств!

уйму треугольников нарисовал.. smile

пока не пойму..может у вас есть какие-нибудь идеи!?

понял только то что квадратные матрицы не подходят, только прямоугольные.

kura1

Дата 16.11.2008, 20:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: нет

ребус не для смертных smile

kura1

Дата 20.11.2008, 23:49 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: нет

SoWa

Дата 21.11.2008, 08:39 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: нет
Всего: 74

Задача на графах решается. Танцуй от этого

--------------------

Всем добра smile

Silent

Дата 23.11.2008, 11:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 1
Всего: 9

Самая первая мысль - полный перебор:

Код


type TPoint=record
       x,y:integer;
     end;
     TArr = array [0..nmax-1] of TPoint;
var a,b:TArr;
    x,y,z:TPoint;
Procedure Init;
begin
//инициализация множеств
end;
Procedure Done;
begin
//вывод решения - точки x,y,z
end;
Function GetCountInside(x:TArr;a,b,c:TPoint):integer;
begin
//возвращает количество точек из множества x,
//лежащих внутри треугольника с вершинами a,b,c
end;
Function Solve:boolean;
var i,j,k:integer
    flag:boolean;
begin
  flag:=true;
  i:=0;
  while (flag)and(i<n) do begin
    j:=i+1;
    while (flag)and(j<n) do begin
      k:=j+1;
      while (flag)and(k<n) do begin
        flag:=GetCountInside(a,a[i],a[j],a[k])<>GetCountInside(b,a[i],a[j],a[k]);
        if flag then inc(k);
      end;
      if flag then inc(j);
    end;
  if flag then inc(i);
  end;
end;
begin
Init;
if Solve then Done
else Write('Решений нет!');
end.

kura1

Дата 5.12.2008, 03:04 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: нет

Цитата(SoWa @ 21.11.2008, 06:39

)

Задача на графах решается. Танцуй от этого

графы не знаю smile

Silent, мысль правильная! а код на СИ++ можно

?

Это сообщение отредактировал(а) kura1 - 5.12.2008, 21:29

kura1

Дата 8.7.2009, 11:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: нет

Silent, тебе спасибо)

2p0i

Дата 9.7.2009, 14:39 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

Репутация: нет
Всего: 1

А в чём прикол? Если вам подходит лобовой алгоритм за O(N^4), то это очень просто пишется.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Интересные и занимательные задачи по программированию \| Следующая тема »