Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/12: Рейтинг темы: голосов - 12, средняя оценка - 4.67
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
1

Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств

08.07.2012, 22:03. Просмотров 2302. Ответов 12
Метки нет (Все метки)

Даны два непересекающихся конечных множества точек на плоскости. Определить окружность, проходящую через k (k>=3) точек каждого из множеств.
Подскажите пожалуйста как решить эту задачу, хотя бы алгоритм решения, я так думал что нужно ввести два массива двумерных размерностью [n][2] в которых содержатся координаты точек потом упорядочить их как на координатной плоскости и уже искать окружность, сдесь то и я застрял, подскажите пожалуйста. Заранее спасибо!
Да окружность должна быть определена центром и радиусом.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.07.2012, 22:03
Ответы с готовыми решениями:

Определить окружность проходящую через k (k>=3) каждого из множеств
Даны два непересекающихся конечных множества точек на плоскости. Определить окружность проходящую...

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

Построить окружность радиуса R, проходящую через точки с заданными координатами
ПОМОГИТЕ! Java Постройте окружность радиуса R, проходящую через точки с координатами (x1; y1) и...

Найти окружность наименьшей длины, проходящую по крайней мере через 3 исходные точки
Дано N точек на плоскости. Найти окружность наименьшей длины, проходящую по крайней мере через 3...

12
Комп_Оратор)
Эксперт по математике/физике
8610 / 4327 / 584
Регистрация: 04.12.2011
Сообщений: 12,926
Записей в блоге: 14
08.07.2012, 23:17 2
Просто размышление вслух:
Вероятность нахождения произвольной точки в произвольной окружности пропорциональна квадрату радиуса. Тогда изменение вероятности в n раз соответствует изменению радиуса в корень из n. Поскольку нет никаких предположений о средней плотности расположения каждого из множеств точек, самый простой но не самый быстрый метод - метод половинного деления. Если размер области задан, то определение максимального размера окружности по её координатам, для первой итерации - простая геометрическая задача. В качестве целевого параметра определяющего, делим радиус на корень из 2 или умножаем, выбираем количество точек в окружности того множества, для которого это количество максимально отличается от заданного k.
Не судите строго. Я не математик.
0
591 / 529 / 76
Регистрация: 22.03.2011
Сообщений: 1,585
09.07.2012, 02:09 3
интересная задача
1
Комп_Оратор)
Эксперт по математике/физике
8610 / 4327 / 584
Регистрация: 04.12.2011
Сообщений: 12,926
Записей в блоге: 14
09.07.2012, 02:27 4
Цитата Сообщение от IGPIGP Посмотреть сообщение
В качестве целевого параметра определяющего,
О нет, то что я придумал вряд ли пригодится. Так как понял, что окружность должна охватывать по k точек. А сказано - проходит через k точек. Причем, не не менее чем через k, а именно через k. То есть при случайном размещении точек, вероятность решения практически нулевая... Да, есть о чём подумать.
0
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
09.07.2012, 06:23  [ТС] 5
Я вот на этом сдесь и залип.
p.s. Мне интересно сдесь всем кто пошел на программиста в универ преподы ничего не объясняли и все приходилось изучать самому? Просто наш, с самого начала сказал что объяснять вам что-то это 20 век, все есть в инете ищите и разбирайтесь сами)
0
Модератор
Эксперт Python
27953 / 14915 / 2936
Регистрация: 12.02.2012
Сообщений: 24,437
Записей в блоге: 4
09.07.2012, 08:20 6
Уточняющий вопрос: для каждого k (>=3) окружность должна проходить через k точек первого множества и k точек второго?

Добавлено через 1 час 12 минут
Есть соображения. Предположим, взято k точек. Через любые три (не лежащие на одной прямой) можно провести единственную окружность. Если остальные k-3 точки не лежат на этой окружности, то набор не подходит.

Вытанцовывается алгоритм:

1) взять три любые точки из набора
2) если они лежат на одной прямой - набор отвергается
3) в противном случае получаем центр и радиус и проверяем остальные k-3 точки на принадлежность
к этой окружности. Если принадлежат - набор в зачёт. Иначе - взять следующий набор.


Ну, и нужно уметь строить ВСЕ наборы по k точек из совокупности n точек (их к-во будет Cnk)
1
Модератор
62498 / 46688 / 32180
Регистрация: 18.05.2008
Сообщений: 112,951
09.07.2012, 09:22 7
Писал я это в Паскале, можете посмотреть, там есть комментарии.
Определить окружность проходящую через k (k>=3) каждого из множеств
1
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
09.07.2012, 11:31  [ТС] 8
Препод сегодня сказал, что нужно брать 3+ точек из одного множества они должны лежать не внутри а на окружности, далее нужно смотреть чтобы нашлись 3 точки из второго множества которые тоже лежать на окружности этой. А так чтобы прога работала от 3 и более точек.

Добавлено через 38 секунд
Puporev, Большое спасибо, попробую разобраться в коде!
0
Модератор
62498 / 46688 / 32180
Регистрация: 18.05.2008
Сообщений: 112,951
09.07.2012, 11:33 9
HarryPhomin, В С++ можно больше точек брать, не Паскаль все же...
1
Комп_Оратор)
Эксперт по математике/физике
8610 / 4327 / 584
Регистрация: 04.12.2011
Сообщений: 12,926
Записей в блоге: 14
09.07.2012, 13:26 10
Цитата Сообщение от Catstail Посмотреть сообщение
1) взять три любые точки из набора
2) если они лежат на одной прямой - набор отвергается
3) в противном случае получаем центр и радиус и проверяем остальные k-3 точки на принадлежность
к этой окружности. Если принадлежат - набор в зачёт. Иначе - взять следующий набор.
Я думаю о чём-то похожем:
Пусть множества точек A и В.
1) Создаём набор для выборки - поисковый набор точек множества A0. Вначале в него входят все точки А.
2) Создаём набор A(3,n) для сохранения окружностей содержащий 3 точки из А и n точек из B. В начале A(3, n) пуст.
3) Из набора A0 выбираем пару точек.
3.1.) Выбираем последовательно по одной точке из A формируя тройку, точки лежащие на прямой пропускаем.
3.2.) Для каждой тройки как только она получена, выбираем последовательно точки из B. Сделав полный перебор B, выясняем принадлежит ли данной окружности заданной А-тройкой три и более точек из B.
-Если да то A-тройка и B-n точек (n>=3) добавляется в набор А(3, n)
-Если нет (даже B-тройки не нашлось), - удаляем исходную пару точек из поискового набора A0.
4. Выбираем следующую пару из A0 п.3.
5. Продолжаем пока в A0 есть три и более точек.
Далее из A-троек точек А(3, n) формируем поисковый набор A1 (его формат - тройки а не отдельные точки как в A1) и пустой набор окружностей А(4,n).
Нас интересуют для A1 только окружности с n>3 (точек B три и более для каждой A-тройки).
теперь же A-тройки уже сформированы и нужно последовательно выбирать четвёртую точку из A.
5.1. Выбираем последовательно из A1 по одной точке не совпадающей с каждой из исходной A-тройки. Проверяем на принадлежность окружности исходной A-тройки.
Если да добавляем полученную А-четвёрку и n из A(3, n) в набор A(4,n).
Если нет, - (для всех последовательно выбранных точек по 5.1) - удаляем запись 3,n из поискового набора A1.
И так пока A1 содержит 4 и более точек.
Далее формируем А2 из полученного A(4,n)....
Рано или поздно для набора Ap не найдётся p точек в наборе A(p-1, n).
Это долго. Но ничего интереснее пока не придумал.
1
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
09.07.2012, 17:24  [ТС] 11
Спасибо, только что пришел с занятий, сейчас прочитаю вдумаюсь да начну делать потихоньку)
0
Модератор
62498 / 46688 / 32180
Регистрация: 18.05.2008
Сообщений: 112,951
09.07.2012, 17:27 12
Знал бы С++, переписал бы...
0
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
10.07.2012, 00:26  [ТС] 13
Puporev, Да ничего и так много мне помогли надо и самому головой поработать)

Добавлено через 6 часов 53 минуты
Все ура, написал задачу проверил для всех случаев, вроде работает без сбоев!
Кому надо текст может быть поможет вот, только данные я вводил из файла задавая сначала координаты иксовые потом игриковые так для каждого множества.

C++
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
 
/*
 * 
 */
int main(int argc, char** argv) {
    int n1, k, i, j, n2, sum=0;
    float a, x1, x2, x3, y1, y2, y3;
    printf("BBedite kolichestvo tochek n1 и n2, a tak zhe kol-vo tochek okruzhnosti :  ");
    scanf("%d%d%d", &n1, &n2, &k);
    printf("\n");
    float arrX[n1], arrY[n1];/*Объявляю массивы первых и вторых координат 1 го множества*/
    float novX[n2], novY[n2];/*Объявляю массивы первых и вторых координат 2 го множества*/
    
    FILE *fl;
    fl=fopen("text.txt", "r");
    /*----------------------------------*/
    printf("1 mnozhestvo:\n\n");/*Сканирую из файла и одновременно вывожу все иксовые координаты первого множества*/
    for(i=1; i<=n1; i++){
        fscanf(fl, "%f", &arrX[i]);
        printf("%d X koordinaty %f \n", i, arrX[i]);
        sum++;
    }
        printf("\n");
   /*-----------------------------------*/ 
        for(i=1; i<=n1; i++){/*Сканирую из файла и одновременно вывожу все игриковые координаты первого множества*/
        fscanf(fl, "%f", &arrY[i]);
        printf("%d Y koordinaty %f \n", i, arrY[i]);
    }
        printf("\n\n\n\n\n");   
                
    /*----------------------------------*/
        printf("2 mnozhestvo:\n\n");/*Сканирую из файла и одновременно вывожу все иксовые координаты второго множества*/
        for(i=1; i<=n2; i++){
        
        fscanf(fl, "%f", &novX[i]);
        printf("%d X koordinaty %f \n", i, novX[i]);
    }
    printf("\n");
    
    /*----------------------------------*/
    
    for(i=1; i<=n2; i++){/*Сканирую из файла и одновременно вывожу все игриковые координаты второго множества*/
        
        fscanf(fl, "%f", &novY[i]);
        printf("%d Y koordinaty %f \n", i, novY[i]);
    }
    printf("\n");
    /*///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////*/
    if(sum<3){
        printf("cherez dannye tochki nelzya provesti pryamuyu");/*если через эти точки первого множества нельзя провести окружность то выводим сообщение и выходим из проги*/
        return;
    }
    /*//////////////////////////////////////////////----------------------------------/////////////////////////////////////*/
    for(i=1; i<=n1; i++){      /*проверяю 1 множество,  можно ли построить в нем окружность по данным точкам*/    
        a=arrX[i] * arrY[i+1] + arrX[i+1] * arrY[i+2] + arrY[i] * arrX[i+2] - arrX[i+2] * arrY[i+1] - arrX[i] * arrY[i+2] - arrX[i+1] * arrY[i];
        printf("%f\n", a);
        if(a!=0){
        x1=arrX[i];
        x2=arrX[i+1];
        x3=arrX[i+2];
        y1=arrY[i];
        y2=arrY[i+1];
        y3=arrY[i+2];
        printf("cherez eti tochki mozhno provesti okruzhnostj %f\n\n", a);
        break;
        }
        else{
            continue;
        }
    }
    if(a==0){
        printf("cherez dannye tochki nelzya provesti pryamuyu\n");/*если через эти точки первого множества нельзя провести окружность то выводим сообщение и выходим из проги*/
        return;
    }
        printf("%f %f\n", x1, y1);/*если можно то выводим сообщение и выводим координаты точек по которым строим окружность тройку точек*/
        printf("%f %f\n", x2, y2);
        printf("%f %f\n", x3, y3);
    /*//////////////////////////////////////////////----------------------------------/////////////////////////////////////*/ 
        float aa[2], bb[2];/*задаю массивы середин сторон вписанного в окружность треугольника вершинами которого являются точки из прошлого пункта*/
        aa[1]=(x1+x2)/2;/*считаю координаты сeредин двух сторон*/
        aa[2]=(x2+x3)/2;
        bb[1]=(y1+y2)/2;
        bb[2]=(y2+y3)/2;
        printf("\n\n%f %f\n", aa[1], bb[1]);
        printf("%f %f\n", aa[2], bb[2]);
      /*//////////////////////////////////////////////----------------------------------/////////////////////////////////////*/
        float x, y, l, ll, o, oo;/*пользуясь геометрической интерприятацией нахожу координаты центра */
        l=x2-x1;
        ll=x3-x2;
        o=y2-y1;
        oo=y3-y2;
        printf("\n\n%f", l);
        printf("\n\n%f", ll);
        printf("\n\n%f", o);
        printf("\n\n%f", oo);
        x=(-o*(ll*aa[2] + oo*bb[2]) + oo*(l*aa[1] + o*bb[1])) / (l*oo - o*ll);
        y=(-ll*(l*aa[1] + o*bb[1]) + l*(ll*aa[2] + oo*bb[2])) / (l*oo - o*ll);
        printf("\n\n%f  %f", x, y);
     /*//////////////////////////////////////////////----------------------------------/////////////////////////////////////*/
        float R;/*нахожу радиус*/
        R=sqrt((x-x3)*(x-x3)+(y-y3)*(y-y3));
        printf("\n\n%f", R);
    /*//////////////////////////////////////////////----------------------------------/////////////////////////////////////*/
        j=0;/*проверяю сколько точек из первого множества удовлетворяют условию, если больше нашего заданного к, то я присваиваю к это количество*/
        float ruv;
        
        for(i=1;i<=n1;i++){
            ruv=sqrt((x-arrX[i])*(x-arrX[i]) + (y-arrY[i])*(y-arrY[i]));
            if(ruv!=R){
                continue;
             }   
            else{  
                j++;
                ruv=0;
            }
        }
        if(j>=k){
            k=j;
        }
        
     /*//////////////////////////////////////////////----------------------------------/////////////////////////////////////*/
        j=0;/*проверяю скока точек из второго множества удовлетворяют условию, если меньше к то выводим сообщение что такой окружности нет, если больше или равно то такая окружность есть */
        float rast=0;
        
        for(i=1;i<=n2;i++){
            rast=sqrt((x-novX[i])*(x-novX[i]) + (y-novY[i])*(y-novY[i]));
            if(rast!=R){
                continue;
             }   
            else{  
                j++;
                rast=0;
            }
        }
        if(j>=k){
            printf("\n\ntakaya okrujnostj sushestvuet ee radius raven %f,\n a koordinaty centra (%f,%f)\n", R, x, y);
        }
        else{
            printf("\npo zadannym tochkam nelza postroitj takuyu okruzhnostj\n");
        }
       
    return (EXIT_SUCCESS);
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.07.2012, 00:26

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

Определить, сколько точек пересечения имеют прямая и окружность и найти координаты этих точек
Привет. Тут такое дело. В общем я неплохо знаю сам язык, но вот задачку решить не могу. Т.е не знаю...

Определить кривую, проходящую через данную точку
Задание: Из семейства кривых, наклон которых равен 2x, определить ту, которая проходит через ( 3;...

Поиск непересекающихся множеств
Помогите составить алгоритм по поиску непересекающихся множеств, очень надо.


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.