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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 5.00
HarryPhomin
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
#1

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

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

Даны два непересекающихся конечных множества точек на плоскости. Определить окружность, проходящую через 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++
Здравствуйте, голову сломал, ища ошибку в задаче Задано два множества точек на плоскости. Первое из них задается уравнением...

На плоскости задано множество точек. Выбрать три различные точки так, чтобы проходящая через них окружность делила это множество на группы - C++
На плоскости задано множество точек. Выбрать три различные точки так, чтобы проходящая через них окружность делила это множество на группы,...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6447 / 3094 / 306
Регистрация: 04.12.2011
Сообщений: 8,567
Записей в блоге: 4
08.07.2012, 23:17 #2
Просто размышление вслух:
Вероятность нахождения произвольной точки в произвольной окружности пропорциональна квадрату радиуса. Тогда изменение вероятности в n раз соответствует изменению радиуса в корень из n. Поскольку нет никаких предположений о средней плотности расположения каждого из множеств точек, самый простой но не самый быстрый метод - метод половинного деления. Если размер области задан, то определение максимального размера окружности по её координатам, для первой итерации - простая геометрическая задача. В качестве целевого параметра определяющего, делим радиус на корень из 2 или умножаем, выбираем количество точек в окружности того множества, для которого это количество максимально отличается от заданного k.
Не судите строго. Я не математик.
OstapBender
583 / 521 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
09.07.2012, 02:09 #3
интересная задача
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6447 / 3094 / 306
Регистрация: 04.12.2011
Сообщений: 8,567
Записей в блоге: 4
09.07.2012, 02:27 #4
Цитата Сообщение от IGPIGP Посмотреть сообщение
В качестве целевого параметра определяющего,
О нет, то что я придумал вряд ли пригодится. Так как понял, что окружность должна охватывать по k точек. А сказано - проходит через k точек. Причем, не не менее чем через k, а именно через k. То есть при случайном размещении точек, вероятность решения практически нулевая... Да, есть о чём подумать.
HarryPhomin
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
09.07.2012, 06:23  [ТС] #5
Я вот на этом сдесь и залип.
p.s. Мне интересно сдесь всем кто пошел на программиста в универ преподы ничего не объясняли и все приходилось изучать самому? Просто наш, с самого начала сказал что объяснять вам что-то это 20 век, все есть в инете ищите и разбирайтесь сами)
Catstail
Модератор
22546 / 10951 / 1776
Регистрация: 12.02.2012
Сообщений: 18,087
09.07.2012, 08:20 #6
Уточняющий вопрос: для каждого k (>=3) окружность должна проходить через k точек первого множества и k точек второго?

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

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

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


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

Добавлено через 38 секунд
Puporev, Большое спасибо, попробую разобраться в коде!
Puporev
Модератор
51859 / 39790 / 13156
Регистрация: 18.05.2008
Сообщений: 91,055
09.07.2012, 11:33 #9
HarryPhomin, В С++ можно больше точек брать, не Паскаль все же...
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6447 / 3094 / 306
Регистрация: 04.12.2011
Сообщений: 8,567
Записей в блоге: 4
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).
Это долго. Но ничего интереснее пока не придумал.
HarryPhomin
1 / 1 / 0
Регистрация: 05.07.2012
Сообщений: 34
09.07.2012, 17:24  [ТС] #11
Спасибо, только что пришел с занятий, сейчас прочитаю вдумаюсь да начну делать потихоньку)
Puporev
Модератор
51859 / 39790 / 13156
Регистрация: 18.05.2008
Сообщений: 91,055
09.07.2012, 17:27 #12
Знал бы С++, переписал бы...
HarryPhomin
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);
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.07.2012, 00:26
Привет! Вот еще темы с ответами:

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

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

Поиск непересекающихся множеств - Delphi
помогите составить алгоритм по поиску непересекающихся множеств, вообще никакой информации не могу найти.

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.07.2012, 00:26
Ответ Создать тему
Опции темы

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