Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 5.00
HarryPhomin
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
08.07.2012, 22:03     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #1
Даны два непересекающихся конечных множества точек на плоскости. Определить окружность, проходящую через k (k>=3) точек каждого из множеств.
Подскажите пожалуйста как решить эту задачу, хотя бы алгоритм решения, я так думал что нужно ввести два массива двумерных размерностью [n][2] в которых содержатся координаты точек потом упорядочить их как на координатной плоскости и уже искать окружность, сдесь то и я застрял, подскажите пожалуйста. Заранее спасибо!
Да окружность должна быть определена центром и радиусом.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2012, 22:03     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств
Посмотрите здесь:

Известны оценки двух учеников по четырём предметам Определить сумму оценок каждого ученика C++
Определить сумму элементов каждого из двух массивов, а также насколько они различаются C++
C++ На плоскости задано множество точек. Выбрать три различные точки так, чтобы проходящая через них окружность делила это множество на группы
C++ Определить, сколько точек пересечения имеют прямая и окружность и найти координаты этих точек
Входит ли точки в треугольник из двух множеств точек C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6167 / 2896 / 282
Регистрация: 04.12.2011
Сообщений: 7,703
Записей в блоге: 3
08.07.2012, 23:17     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #2
Просто размышление вслух:
Вероятность нахождения произвольной точки в произвольной окружности пропорциональна квадрату радиуса. Тогда изменение вероятности в n раз соответствует изменению радиуса в корень из n. Поскольку нет никаких предположений о средней плотности расположения каждого из множеств точек, самый простой но не самый быстрый метод - метод половинного деления. Если размер области задан, то определение максимального размера окружности по её координатам, для первой итерации - простая геометрическая задача. В качестве целевого параметра определяющего, делим радиус на корень из 2 или умножаем, выбираем количество точек в окружности того множества, для которого это количество максимально отличается от заданного k.
Не судите строго. Я не математик.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
09.07.2012, 02:09     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #3
интересная задача
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6167 / 2896 / 282
Регистрация: 04.12.2011
Сообщений: 7,703
Записей в блоге: 3
09.07.2012, 02:27     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #4
Цитата Сообщение от IGPIGP Посмотреть сообщение
В качестве целевого параметра определяющего,
О нет, то что я придумал вряд ли пригодится. Так как понял, что окружность должна охватывать по k точек. А сказано - проходит через k точек. Причем, не не менее чем через k, а именно через k. То есть при случайном размещении точек, вероятность решения практически нулевая... Да, есть о чём подумать.
HarryPhomin
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
09.07.2012, 06:23  [ТС]     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #5
Я вот на этом сдесь и залип.
p.s. Мне интересно сдесь всем кто пошел на программиста в универ преподы ничего не объясняли и все приходилось изучать самому? Просто наш, с самого начала сказал что объяснять вам что-то это 20 век, все есть в инете ищите и разбирайтесь сами)
Catstail
Модератор
 Аватар для Catstail
21452 / 10237 / 1667
Регистрация: 12.02.2012
Сообщений: 17,114
09.07.2012, 08:20     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #6
Уточняющий вопрос: для каждого k (>=3) окружность должна проходить через k точек первого множества и k точек второго?

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

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

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


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

Добавлено через 38 секунд
Puporev, Большое спасибо, попробую разобраться в коде!
Puporev
Модератор
 Аватар для Puporev
50390 / 38321 / 12276
Регистрация: 18.05.2008
Сообщений: 86,767
09.07.2012, 11:33     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #9
HarryPhomin, В С++ можно больше точек брать, не Паскаль все же...
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6167 / 2896 / 282
Регистрация: 04.12.2011
Сообщений: 7,703
Записей в блоге: 3
09.07.2012, 13:26     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #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).
Это долго. Но ничего интереснее пока не придумал.
HarryPhomin
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
09.07.2012, 17:24  [ТС]     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #11
Спасибо, только что пришел с занятий, сейчас прочитаю вдумаюсь да начну делать потихоньку)
Puporev
Модератор
 Аватар для Puporev
50390 / 38321 / 12276
Регистрация: 18.05.2008
Сообщений: 86,767
09.07.2012, 17:27     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #12
Знал бы С++, переписал бы...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.07.2012, 00:26     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств
Еще ссылки по теме:

C++ Указать (n-1)-звенную несамопересекающуюся замкнутую ломаную, проходящую через заданные точки
C++ Определить количество точек пересечения двух окружностей
C++ Составить уравнение плоскости проходящую через прямую

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

Или воспользуйтесь поиском по форуму:
HarryPhomin
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
10.07.2012, 00:26  [ТС]     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств #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);
}
Yandex
Объявления
10.07.2012, 00:26     Определить окружность, проходящую через k (k>=3) точек каждого из двух непересекающихся множеств
Ответ Создать тему
Опции темы

Текущее время: 13:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru