Дано n точек на плоскости: найти окружность на заданных точках и содержащую наибольшее число заданных точек.
Буду очень признателен, если кто поможет написать программу!
Полная версия: Геометрическая задача
Berline
Что это значит? То есть как можно больше точек должны лежать на самой окружности, или круг должен содержать как можно больше точек? (по второму варианту есть вот эта задача)...
Цитата
содержащую наибольшее число заданных точек
Что это значит? То есть как можно больше точек должны лежать на самой окружности, или круг должен содержать как можно больше точек? (по второму варианту есть вот эта задача)...
volvo
как я мог понять, то окружность должна содержать в себе максимальное число точек! Но не понятно одно, для построения окружности нуна 2 точки: 1 - центр, 2 - я, с помощью которой получится радиус! тада ведь мона постоить окружность содержащую все заданные точки...
как я мог понять, то окружность должна содержать в себе максимальное число точек! Но не понятно одно, для построения окружности нуна 2 точки: 1 - центр, 2 - я, с помощью которой получится радиус! тада ведь мона постоить окружность содержащую все заданные точки...
Berline
Для однозначного задания окружности достаточно трех точек, но эта окружность не обязательно будет содержать остальные.
Для однозначного задания окружности достаточно трех точек, но эта окружность не обязательно будет содержать остальные.
volvo
в пространстве нуны действительно 3, но на плоскости-то 2...
переделать прогу из вышеизложенной ссылки я не смогу, т.к. с паскалем на вы...
в пространстве нуны действительно 3, но на плоскости-то 2...
переделать прогу из вышеизложенной ссылки я не смогу, т.к. с паскалем на вы...
Berline, ты ошибаешься, для построения окружности надо 3 точки на плоскости. (лежащие на окружности).
Видимо надо найти 3 точки, такие чтьо окружность на этих 3 точках содержит макс. число других заданных точек...
Код
найти окружность на заданных точках
Видимо надо найти 3 точки, такие чтьо окружность на этих 3 точках содержит макс. число других заданных точек...
перебираешь тройки точек, находишь центр , и проверешь сколько точек внутри лежат...
Berline, а ты не из МИЭМ часом ? 
:p2:
:p2:
Oleg_Z
may be...
may be...
я бы воспользовался старым добрым брутфорсом. Принцип примерно такой:
1). Берём очередную тройку точек.
2). Вычисляем центр окпужности лежащей на них (x,y).
3). Вычисляем её радиус как расстояние до любой из выбранных точек ®.
4). Смотрим сколько ещё точек лежит на этой окружности (перебираем все остальные и подставляем в уравнение окружности).
5). Сравниваем с предыдущим ерзультатом: надо - сохраняем, не надо - забиваем...
Куда уж проще-то...
1). Берём очередную тройку точек.
2). Вычисляем центр окпужности лежащей на них (x,y).
3). Вычисляем её радиус как расстояние до любой из выбранных точек ®.
4). Смотрим сколько ещё точек лежит на этой окружности (перебираем все остальные и подставляем в уравнение окружности).
5). Сравниваем с предыдущим ерзультатом: надо - сохраняем, не надо - забиваем...
Куда уж проще-то...
ShadowWatcher
в теории эт понятно, но на практике... завтра пообсчаюсь с Oleg_Z'ом, авось что прояснится, если нет, бу здесь искать дальше помощи!
в теории эт понятно, но на практике... завтра пообсчаюсь с Oleg_Z'ом, авось что прояснится, если нет, бу здесь искать дальше помощи!
Так ты поясни в каком именно моменте у тебя проблема. Разберёмся прямо здесь и сейчас...
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 проверяет лежит ли точка на окружности указанного радиуса и с центром в указанноё точке.
Написал бы и их, но геометрию уже забывать начал да и компилятора под рукой нет... А так думаю, что принцип можно понять, а дописать особого труда не составит даже для начинающего
Код
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 проверяет лежит ли точка на окружности указанного радиуса и с центром в указанноё точке.
Написал бы и их, но геометрию уже забывать начал да и компилятора под рукой нет... А так думаю, что принцип можно понять, а дописать особого труда не составит даже для начинающего
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 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
For j:=i + 1 To Count-1 Do
For k:=j + 1 To Count Do
Oleg_Z, не обижайся, но не тебе меня учить.
Как правило, если индексация с нуля, а кол-во элементов = Count, то последний элемент имеет индекс Count-1.
Как правило, если индексация с нуля, а кол-во элементов = Count, то последний элемент имеет индекс Count-1.
ShadowWatcher, не обижайся, но не тебе со мной спорить.
Я рассматриваю адресацию как это обычно у людей бывает - с единицы.
Я рассматриваю адресацию как это обычно у людей бывает - с единицы.
Oleg_Z, ну и не тебе со мной. Поверь ты мне - у меня практики куда больше, чем у тебя, и адресация у меня как правило (за исключением ОЧЕНЬ РЕДКИХ исключений) начинается с нуля.
ShadowWatcher
Цитата
ПРАВИЛА РАЗДЕЛА!!!
...
7. НЕ используйте форум для личного общения, все что не относиться к обсуждению темы на PM!
...
7. НЕ используйте форум для личного общения, все что не относиться к обсуждению темы на PM!
Цитата
Поверь ты мне - у меня практики куда больше, чем у тебя
Это абсолютно не важно.
Цитата
адресация у меня как правило
Вот видишь, говорю же что у тебя не как у людей.
ЗЫ: volvo прав, нарушаешь правила форума....
Предлагаю следующее:
1) адресация у людей - вещь достаточно неопределенная, т. к. человеческий мозг имеет архитектуру, отличную от фон-неймановской ;);
2) возможно, ShadowWatcher много пишет на C, С++ или ассемблере, поэтому привык к индексации от 0;
3) не стоит ссориться из-за пустяков :D.
Добавлю, что индексация от любого значения не влияет на производительность кода, т. к. компилятор всего-лишь корректирует на стадии компиляции начальный адрес массива.
1) адресация у людей - вещь достаточно неопределенная, т. к. человеческий мозг имеет архитектуру, отличную от фон-неймановской ;);
2) возможно, ShadowWatcher много пишет на C, С++ или ассемблере, поэтому привык к индексации от 0;
3) не стоит ссориться из-за пустяков :D.
Добавлю, что индексация от любого значения не влияет на производительность кода, т. к. компилятор всего-лишь корректирует на стадии компиляции начальный адрес массива.
xds, согласен.
По пункту 2: сейчас пишу на Delphi/C# - тут везде адресация с 0 (в Delphi, т. к. в проекте таких масштабов массивы за даром не нужны, а в списках...)
Так что замнём эту тему
По пункту 2: сейчас пишу на Delphi/C# - тут везде адресация с 0 (в Delphi, т. к. в проекте таких масштабов массивы за даром не нужны, а в списках...)
Так что замнём эту тему
ShadowWatcher, согласен, закатаем эту тему в асфальт.
хм... это мысль ...
Цитата
человеческий мозг имеет архитектуру, отличную от фон-неймановской ;
хм... это мысль ...
а программу я так и не написал... 
:p2:
:p2:
постараюсь написать сегодня...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.