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

Минимальное число точек в описанном радиусе - C++

Восстановить пароль Регистрация
 
Bloodykeeper
This party getting crazy!
 Аватар для Bloodykeeper
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
17.03.2010, 20:28     Минимальное число точек в описанном радиусе #1
Задано множество из m точек на плоскости. Найти такую из них, что круг заданного радиуса с центром в этой точке содержит минимальное число точек из данного множества точек. Как сделать такую задачу? раньше ничего подобного не делал... Помогите пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.03.2010, 20:28     Минимальное число точек в описанном радиусе
Посмотрите здесь:

минимальное число в последовательности C++
C++ Минимальное число шагов
Минимальное число в матрице C++
Минимальное число C++
C++ максимальное и минимальное число
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Грымзик
 Аватар для Грымзик
2466 / 1443 / 31
Регистрация: 14.09.2009
Сообщений: 2,742
17.03.2010, 21:22     Минимальное число точек в описанном радиусе #2
А что именно не понятно? Если дан радиус, то определить сколько точек из заданного множества лежит внутри окружности элементарно. Поэтому и остается просто перебрать все точки в качестве центра окружности.
Зоти Сергей
 Аватар для Зоти Сергей
228 / 226 / 13
Регистрация: 18.12.2009
Сообщений: 316
17.03.2010, 21:57     Минимальное число точек в описанном радиусе #3
Сделал так, что если случилось так, что несколько точек имеют одинаковое минимальное количество точек входящих в окружность образованную заданным радиусом, то они будут все распечатаны.
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
//---------------------------------------------------------------------------
#include <conio.h>
#include <complex.h>
#include <iostream.h>
//---------------------------------------------------------------------------
typedef complex<double>Complex;
struct CPointMass
{
    Complex Point;
        int Mass;
};
int main(int argc, char* argv[])
{
    int PointsAmount;
        CPointMass * Points;
        double x,y, Radius;
        int i,j;
        cout << "Введите радиус: ";
        cin >> Radius;
        cout << "Введите кол-во точек: ";
        cin >> PointsAmount;
        if(!PointsAmount)
        return 0;
        Points = new CPointMass[PointsAmount];
        for(i=0;i<PointsAmount;i++)
        {
            cout << "Введите X"<<i<<" : ";
            cin>>x;
                cout << "Введите Y"<<i<<" : ";
            cin>>y;
                Points[i].Point=Complex(x,y);
                Points[i].Mass=0;
        }
        unsigned int MinMass=4294967295;       
        Complex ReqPoint;
        bool Founded=false;
        for(i=0;i<PointsAmount;i++)
        {
            for(j=0;j<PointsAmount;j++)
                {
                    if(abs(Points[i].Point-Points[j].Point)<Radius&&Points[i].Point!=Points[j].Point)
                            Points[i].Mass++;
 
                }
                if(Points[i].Mass<MinMass&&Points[i].Mass>0)
                {
                    ReqPoint=Points[i].Point;
                        MinMass=Points[i].Mass;
                        Founded=true;
                }
        }
        if(!Founded)
            cout<<"Ни одна точка не входит в окружность с заданным радиусом";
        else
            for(i=0;i<PointsAmount;i++)
                {
                    if(Points[i].Mass==MinMass)
                    printf("Найденная точка (x;y)=(%0.3f;%0.3f)\n",real(Points[i].Point),imag(Points[i].Point));
                }
        delete [] Points;
        getch();
}
//---------------------------------------------------------------------------
Bloodykeeper
This party getting crazy!
 Аватар для Bloodykeeper
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
17.03.2010, 22:23  [ТС]     Минимальное число точек в описанном радиусе #4
Зоти Сергей, Спасибо. А как можно на язык Си перевести? *забыл указать...((*
Genius Ignat
17.03.2010, 22:28
  #5

Не по теме:


Скажи преподавателю: "А чем C++ хуже C..."

Bloodykeeper
This party getting crazy!
 Аватар для Bloodykeeper
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
18.03.2010, 08:23  [ТС]     Минимальное число точек в описанном радиусе #6

Не по теме:

не скажу. Я изучаю язык Си а не С++.

Помогите перевести на Си.

Добавлено через 9 часов 45 минут
тема ещё актуальна
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2010, 16:04     Минимальное число точек в описанном радиусе
Еще ссылки по теме:

C++ Минимальное кол-во прямых через заданное множество точек
C++ Отпечатать расстояния от начала координат для тех точек,которые принадлежат кругу с заданным радиусом, и число таких точек.
Задать массив точек, и определить радиус и центр окружности, на которой лежит наибольшее число точек C++

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

Или воспользуйтесь поиском по форуму:
Зоти Сергей
 Аватар для Зоти Сергей
228 / 226 / 13
Регистрация: 18.12.2009
Сообщений: 316
20.03.2010, 16:04     Минимальное число точек в описанном радиусе #7
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
//---------------------------------------------------------------------------
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
//---------------------------------------------------------------------------
#define true  1
#define false 0
//---------------------------------------------------------------------------
typedef struct
{
    double x;
        double y;
}Complex;
//---------------------------------------------------------------------------
double _abs(Complex a, Complex b)
{
    return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
//---------------------------------------------------------------------------
typedef struct
{
        Complex Point;
        int Mass;
}CPointMass;
//---------------------------------------------------------------------------
typedef int bool;
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
    int PointsAmount;
        char TextBuffer[255];
        CPointMass * Points;
        double x,y, Radius;
        int i,j;
        unsigned int MinMass=4294967295;
        Complex ReqPoint;
        bool Founded=false;
        printf("Ââåäèòå Г°Г*äèóñ: ");
        gets(TextBuffer);
        Radius=atof(TextBuffer);
        printf("Ââåäèòå êîë-ГўГ® òî÷åê: ");
        gets(TextBuffer);
        PointsAmount=atoi(TextBuffer);;
        if(!PointsAmount)
                return 0;
        Points = (CPointMass*)malloc(sizeof(CPointMass)*PointsAmount);
        for(i=0;i<PointsAmount;i++)
        {
                printf("Ââåäèòå X %d : ",i);
                gets(TextBuffer);
            Points[i].Point.x=atof(TextBuffer);
                printf("Ââåäèòå Y %d : ",i);
                gets(TextBuffer);
            Points[i].Point.y=atof(TextBuffer);
                Points[i].Mass=0;
        }
        for(i=0;i<PointsAmount;i++)
        {
                for(j=0;j<PointsAmount;j++)
                {
                        if(_abs(Points[i].Point,Points[j].Point)<Radius&&Points[i].Point.x!=Points[j].Point.x&&Points[i].Point.y!=Points[j].Point.y)
                                Points[i].Mass++;
 
                }
                if(Points[i].Mass<MinMass&&Points[i].Mass>0)
                {
                        ReqPoint=Points[i].Point;
                        MinMass=Points[i].Mass;
                        Founded=true;
                }
        }
        if(!Founded)
                printf("ГЌГЁ îäГ*Г* òî÷êГ* Г*ГҐ âõîäèò Гў îêðóæГ*îñòü Г± Г§Г*Г¤Г*Г*Г*ûì Г°Г*äèóñîì");
        else
                for(i=0;i<PointsAmount;i++)
                {
                        if(Points[i].Mass==MinMass)
                                printf("ГЌГ*éäåГ*Г*Г*Гї òî÷êГ* (x;y)=(%0.3f;%0.3f)\n",Points[i].Point.x,Points[i].Point.y);
                }
        free(Points);
        getch();
    return 0;
}
//---------------------------------------------------------------------------
Yandex
Объявления
20.03.2010, 16:04     Минимальное число точек в описанном радиусе
Ответ Создать тему
Опции темы

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