Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 56

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

19.05.2013, 20:44. Показов 1537. Ответов 15
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Ребят помогите пожалуйста.
На плоскости заданы множество точек А и множество окружностей В. Найдите две такие различные точки из А, что проходящая через них прямая пересекается с максимальным количеством окружностей из В.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
19.05.2013, 20:44
Ответы с готовыми решениями:

Интересная геометрическая задача
Добрый день! У меня возникла проблема с интересным заданием. Задача звучит так : даны 2 квадрата, известны координаты их вершин (в...

Реализовать интерфейс геометрическая фигура
Всем привет. Есть такая задача Создать классы квадратов и окружностей, реализующие общий интерфейс «Геометрические фигуры»: ...

Разработать абстрактный класс Геометрическая Фигура
Разработать абстрактный класс ГеометрическаяФигура со свойствами ПлощадьФигуры и ПериметрФигуры. Разработать классы-наследники: ...

15
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
19.05.2013, 21:43
Гузель23, очень сложная задача. Если у вас нет идей как сделать, то вы даже готовое решение не поймете.
0
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 56
20.05.2013, 10:42  [ТС]
эта задача обсуждалась на этом форуме и есть решение на паскале. с ходом действий вроде разобралась, не знаю как реализовать на c#.
вот сама задача:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
uses crt;
type point=record{точки}
           x,y:real;
           end;
     okr=record{окружности}
         x,y,r:real;
         end;
const nmax=20;
function Peres(a,b:point;c:okr):boolean;{пересекаются или нет}
var s,ab,h:real;
begin
s:=abs(a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y));{удвоенная площадь треугольника
вершины которого центр окружности и 2 точки}
ab:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));{сторона, противоположная центру окружности}
h:=s/ab;{высота на нее=расстояние от центра до прямой}
Peres:=h<c.r;{если лно меньше радиуса, пересекаются}
end;
var a:array[1..nmax] of point;
    b:array[1..nmax] of okr;
    n,m,i,j,k,p,mx,imx,jmx:integer;
begin
clrscr;
randomize;
repeat
write('Количество точек до ',nmax,' n=');
readln(n);
until n in [1..nmax];
repeat
write('Количество окружностей до ',nmax,' m=');
readln(m);
until m in [1..nmax];
for i:=1 to n do
 begin
  a[i].x:=-10+random*21;
  a[i].y:=-10+random*21;
 end;
for i:=1 to m do
 begin
  b[i].x:=-5+11*random;
  b[i].y:=-5+11*random;
  b[i].r:=5*random;
 end;
writeln('Координаты точек:');
write('X:');
for i:=1 to n do
write(a[i].x:6:2);
writeln;
write('Y:');
for i:=1 to n do
write(a[i].y:6:2);
writeln;
writeln;
writeln('Параметры окружностей:');
write('X:');
for i:=1 to m do
write(b[i].x:6:2);
writeln;
write('Y:');
for i:=1 to m do
write(b[i].y:6:2);
writeln;
write('R:');
for i:=1 to m do
write(b[i].r:6:2);
writeln;
writeln;
mx:=0;
imx:=0;
jmx:=0;
for i:=1 to n-1 do
for j:=i+1 to n do
 begin
  k:=0;
  for p:=1 to m do
  if Peres(a[i],a[j],b[p]) then k:=k+1;
  if k>mx then
   begin
    mx:=k;
    imx:=i;
    jmx:=j;
   end;
 end;
if mx=0 then write('Нет пересекающихся прямых и окружностей')
else
 begin
  writeln('Максимальное число пересечений прямой с окружностями=',mx);
  write('Эта прямая проходит через точки (',a[imx].x:0:2,';',a[imx].y:0:2,') и (',a[jmx].x:0:2,';',a[jmx].y:0:2,')');
 end;
readln
end.
Добавлено через 12 часов 48 минут
Вы сможете мне помочь?
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
20.05.2013, 10:43
Гузель23, я не уверен, что рекурсивный метод с циклами тройной вложенности не повиснет на моем восьмиядерном процессоре...
0
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 56
20.05.2013, 10:45  [ТС]
Все так безнадежно?
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
20.05.2013, 10:46
Гузель23, этот код - увы. Даже если он рабочий. Стек не выдержит такого издевательства.
0
 Аватар для LeniumSoft
1454 / 847 / 150
Регистрация: 06.06.2012
Сообщений: 2,370
20.05.2013, 10:49
Цитата Сообщение от Psilon Посмотреть сообщение
я не уверен, что рекурсивный метод с циклами тройной вложенности не повиснет на моем восьмиядерном процессоре...
Не повиснет! У меня обучение нейронной сети методом обратного распространения ошибки не виснет. А вложенность там похлеще будет! Тут вопрос в правильной реализации. Если эта вложенность сделана правильно, то и отработает вполне быстро.
0
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 56
20.05.2013, 10:49  [ТС]
А вы можете хотя бы алгоритм набросать?
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
20.05.2013, 10:54
LeniumSoft, если вложенность линейная - то фиг там не повиснет. А тот чуть ли не 2n
0
 Аватар для memphis
740 / 284 / 83
Регистрация: 12.12.2012
Сообщений: 564
21.05.2013, 03:30
Psilon, мне кажется Вы несколько сгущаете краски. Задача не так сложна, как кажется на первый взгляд.
Вот код Pascal, который приводит Гузель23. Я попытался его отформатировать, как смог. Рекурсии там вроде нет.
Кликните здесь для просмотра всего текста

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
uses crt;
 
type point = record{точки}
           x, y: real;
        end;
     okr = record{окружности}
         x, y, r: real;
        end;
        
const nmax = 20;
 
function Peres(a, b: point; c: okr): boolean;{пересекаются или нет}
var
    s, ab, h: real;
begin
    s:= abs(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)); {удвоенная площадь треугольника вершины которого центр окружности и 2 точки}
    ab:= sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); {сторона, противоположная центру окружности}
    h:= s / ab; {высота на нее = расстояние от центра до прямой}
    Peres:= h < c.r;{если оно меньше радиуса, пересекаются}
end;
 
var a: array[1..nmax] of point;
    b: array[1..nmax] of okr;
    n, m, i, j, k, p, mx, imx, jmx: integer;
begin
    clrscr;
    randomize;
    
    repeat
        write('Количество точек до ', nmax, ' n = ');
        readln(n);
    until n in [1..nmax];
    
    repeat
        write('Количество окружностей до ', nmax, ' m = ');
        readln(m);
    until m in [1..nmax];
    
    for i:=1 to n do
    begin
        a[i].x:= -10 + random * 21;
        a[i].y:= -10 + random * 21;
    end;
     
    for i:=1 to m do
    begin
        b[i].x:= -5 + 11 * random;
        b[i].y:= -5 + 11 * random;
        b[i].r:= 5 * random;
    end;
     
    writeln('Координаты точек:');
    write('X:');
    
    for i:= 1 to n do
        write(a[i].x:6:2);
    
    writeln;
    write('Y:');
    
    for i:=1 to n do
        write(a[i].y:6:2);
    
    writeln;
    writeln;
    writeln('Параметры окружностей:');
    write('X:');
    
    for i:= 1 to m do
        write(b[i].x:6:2);
    
    writeln;
    write('Y:');
    
    for i:= 1 to m do
        write(b[i].y:6:2);
    
    writeln;
    write('R:');
    
    for i:= 1 to m do
        write(b[i].r:6:2);
    
    writeln;
    writeln;
    
    mx:= 0;
    imx:= 0;
    jmx:= 0;
    
    for i:= 1 to n - 1 do
        for j:= i + 1 to n do
        begin
            k:= 0;
            for p:= 1 to m do
                if Peres(a[i], a[j], b[p]) then
                    k:= k + 1;
            
            if k > mx then
                begin
                    mx:= k;
                    imx:= i;
                    jmx:= j;
                end;
        end;
    
    if mx = 0 then
        write('Нет пересекающихся прямых и окружностей')
    else
        begin
            writeln('Максимальное число пересечений прямой с окружностями=', mx);
            write('Эта прямая проходит через точки (', a[imx].x:0:2, ';', a[imx].y:0:2, ') и (', a[jmx].x:0:2, ';', a[jmx].y:0:2, ')');
        end;
    readln
end.


Гузель23, дайте ссылку на эту Pascal-ную тему. Хочу посмотреть как там люди отписались по работе этого кода. А то мне не всё понятно по части его геометрии.
0
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 56
21.05.2013, 07:42  [ТС]
Найти две такие различные точки из А, что проходящая через них прямая пересекается максимальным количеством окружностей
но тут нет обсуждений даже..


а возможно эту программу перевести на c#?
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
21.05.2013, 08:10
Тут не учитывается, сколько раз оно пересекает окружность, точка может быть внутри круга.
0
 Аватар для memphis
740 / 284 / 83
Регистрация: 12.12.2012
Сообщений: 564
21.05.2013, 16:36
Поковырялся в вики. Геометрия верна.
Цитата Сообщение от Гузель23 Посмотреть сообщение
а возможно эту программу перевести на c#?
А почему нет? Посмотрел в каких темах вы участвуете. С Паскалем вы знакомы, с Шарпом ещё больше. Программа несложная. Нужно только учесть, что в Шарпе индексация массива с нуля.
А я пока пойду плюсану автору паскалевского кода. А то человек честно помог, а ему даже не хмыкнули в ответ.
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
21.05.2013, 17:29
memphis, и мне покажите, тоже плюсану.
Хотя если точки находятся с одной стороны от окружности. по-моему это не учитывается.
0
 Аватар для memphis
740 / 284 / 83
Регистрация: 12.12.2012
Сообщений: 564
21.05.2013, 18:21
Цитата Сообщение от Psilon Посмотреть сообщение
и мне покажите, тоже плюсану.
О, если вы про тему на Паскале, так Гузель23, привела ссылку. Она на этой же странице. Второе сообщение сверху.

Цитата Сообщение от Psilon Посмотреть сообщение
Хотя если точки находятся с одной стороны от окружности. по-моему это не учитывается.
Честно говоря, я не очень понимаю эти Ваши опасения. В то же время Ваше мнение для меня весьма весомое. Давайте разбираться. Допускаю даже, что окажется, что я погорячился.

Я собирался решать это по-другому. Подключить ан. геометр. - мне так понятнее. Но сейчас это не имеет значения...
Как бы тело самой программы у меня не вызывало сомнения. Перебираются точки из A (по которым строятся прямые). Для каждой пары этих точек (читай для каждой прямой) проверяется как далеко от прямой отстоит центр окружности из B. Если это расстояние больше R... впрочем тут Вы и сами прекрасно разбираетесь.

Pascal
1
2
3
4
5
6
7
8
9
function Peres(a, b: point; c: okr): boolean;{пересекаются или нет}
var
    s, ab, h: real;
begin
    s:= abs(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)); {удвоенная площадь треугольника вершины которого центр окружности и 2 точки}
    ab:= sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); {сторона, противоположная центру окружности}
    h:= s / ab; {высота на нее = расстояние от центра до прямой}
    Peres:= h < c.r;{если оно меньше радиуса, пересекаются}
end;
Это самая главная часть. Именно она проверяет наличие пересечения... И опять же - это Вы тоже и без меня знаете.
Вот, думаю где-то в этой функции нам и надо искать консенсус.
Работает это так... А впрочем зачем мне повторять комментарии в функции.
Лучше уточните картину, которая вас смущает. Что значит "точки находятся с одной стороны от окружности"? Я не вижу в этом ничего страшного.
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
21.05.2013, 19:27
memphis, не, алгоритм верный, просто видимо не выспался когда говорил К вечеру все прояснилось.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
21.05.2013, 19:27
Помогаю со студенческими работами здесь

Создание с классов Геометрическая фигура, Треугольник и Окружность
Создайте базовый класс Геометрическая фигура, предусмотрите в нем общие поля/свойства, например координаты центра фигуры, с помощью...

Разработать абстрактный класс «Геометрическая фигура» с возможностью вычислить площадь и периметр фигуры
Разработать абстрактный класс «Геометрическая фигура» с возможностью вычислить площадь и периметр фигуры. Разработать подкласса:...

Дан абстрактный класс «Геометрическая фигура», внутри него определить абстрактные и (или) виртуальные методы
Здравствуйте, помогите пожалуйста с данной задачей: Дан абстрактный класс «Геометрическая фигура», внутри него определить абстрактные и...

Дан абстрактный класс «Геометрическая фигура», внутри него определить абстрактные и (или) виртуальные методы
Дан абстрактный класс «Геометрическая фигура», внутри него определить абстрактные и (или) виртуальные методы. Производным классом...

геометрическая задачка
написать выражение для объема V конуса как функции его боковой поверхности S при данной образующей l=2


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru