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

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

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

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

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

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

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

15
Master of Orion
Эксперт .NET
 Аватар для Psilon
6101 / 4957 / 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
6101 / 4957 / 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
6101 / 4957 / 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
6101 / 4957 / 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
6101 / 4957 / 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
6101 / 4957 / 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
6101 / 4957 / 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
Ответ Создать тему
Новые блоги и статьи
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru