Геометрическая задача Опции

[Berline]

Дано n точек на плоскости: найти окружность на заданных точках и содержащую наибольшее число заданных точек.

Буду очень признателен, если кто поможет написать программу!

[volvo]

Berline

содержащую наибольшее число заданных точек

Что это значит? То есть как можно больше точек должны лежать на самой окружности, или круг должен содержать как можно больше точек? (по второму варианту есть вот эта задача)...

[Berline]

volvo
как я мог понять, то окружность должна содержать в себе максимальное число точек! Но не понятно одно, для построения окружности нуна 2 точки: 1 - центр, 2 - я, с помощью которой получится радиус! тада ведь мона постоить окружность содержащую все заданные точки...

[volvo]

Berline
Для однозначного задания окружности достаточно трех точек, но эта окружность не обязательно будет содержать остальные.

[Berline]

volvo
в пространстве нуны действительно 3, но на плоскости-то 2...
переделать прогу из вышеизложенной ссылки я не смогу, т.к. с паскалем на вы...

[Altair]

Berline, ты ошибаешься, для построения окружности надо 3 точки на плоскости. (лежащие на окружности).

Код

найти окружность на заданных точках

Видимо надо найти 3 точки, такие чтьо окружность на этих 3 точках содержит макс. число других заданных точек...

[Altair]

перебираешь тройки точек, находишь центр , и проверешь сколько точек внутри лежат...

[Altair]

Berline, а ты не из МИЭМ часом ? :p2:

[Berline]

Oleg_Z
may be...

[ShadowWatcher]

я бы воспользовался старым добрым брутфорсом. Принцип примерно такой:
1). Берём очередную тройку точек.
2). Вычисляем центр окпужности лежащей на них (x,y).
3). Вычисляем её радиус как расстояние до любой из выбранных точек ®.
4). Смотрим сколько ещё точек лежит на этой окружности (перебираем все остальные и подставляем в уравнение окружности).
5). Сравниваем с предыдущим ерзультатом: надо - сохраняем, не надо - забиваем...

Куда уж проще-то...

[Berline]

ShadowWatcher
в теории эт понятно, но на практике... завтра пообсчаюсь с Oleg_Z'ом, авось что прояснится, если нет, бу здесь искать дальше помощи!

[ShadowWatcher]

Так ты поясни в каком именно моменте у тебя проблема. Разберёмся прямо здесь и сейчас...

[Berline]

ShadowWatcher
проблема в том, что я паскалем я на вы, и написать прогу не могу, примитив(что нить про матрицу и поиск в ней какой нить строки) я ещё додумался как написать, а тут я ненаю даж что мине сделать, и как быть!

[ShadowWatcher]

Перебор сделать легко:

Код

For i:= 0 To Count-3 Do
 For j:=i + 1 To Count-2 Do
   For k:=j + 1 To Count-1 Do
   Begin
     GetRoundCenterAndRadius(x[i],y[i],x[j],y[j],x[k],y[k],NewCenterX,NewCenterY,NewR);
     NewCount := 0;
     For l:=0 To Count Do
       If PointOnRound(NewCenterX,NewCenterY,NewR,x[l],y[l]) Then
         Inc(NewCount);
     If NewCount > CurrentCount Then
     Begin
       CurrentCenterX := NewCenterX;
       CurrentCenterY := NewCenterY;
       CurrentR := NewR
     End
   End;
 WriteLn('Center: (',CurrentCenterX,';',CurrentCenterY.')');
 WriteLn('Radius: ',CurrentR)

Предполагается, что процедура GetRoundCenterAndRadius по координатам трёх точек возвращает центр и радиус окружности, на которой они лежат, а функция PointOnRound проверяет лежит ли точка на окружности указанного радиуса и с центром в указанноё точке.

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

[Altair]

ShadowWatcher? у тебя перебор неправильный, он не все переберет...

For i:= 0 To Count-3 Do
For j:=i + 1 To Count-2 Do
For k:=j + 1 To Count-1 Do

Все-таки так:

Код

For i:= 0 To Count-2 Do
For j:=i + 1 To Count-1 Do
  For k:=j + 1 To Count Do

[ShadowWatcher]

Oleg_Z, не обижайся, но не тебе меня учить.
Как правило, если индексация с нуля, а кол-во элементов = Count, то последний элемент имеет индекс Count-1.

[Altair]

ShadowWatcher, не обижайся, но не тебе со мной спорить.
Я рассматриваю адресацию как это обычно у людей бывает - с единицы.

[ShadowWatcher]

Oleg_Z, ну и не тебе со мной. Поверь ты мне - у меня практики куда больше, чем у тебя, и адресация у меня как правило (за исключением ОЧЕНЬ РЕДКИХ исключений) начинается с нуля.

[volvo]

ShadowWatcher

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

[Altair]

Поверь ты мне - у меня практики куда больше, чем у тебя

Это абсолютно не важно.

адресация у меня как правило

Вот видишь, говорю же что у тебя не как у людей.

ЗЫ: volvo прав, нарушаешь правила форума....