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

деление множество точек на две равные части - C++

Восстановить пароль Регистрация
 
Suares
0 / 0 / 0
Регистрация: 28.02.2013
Сообщений: 106
31.01.2014, 17:47     деление множество точек на две равные части #1
Есть у меня множество точек и окружность с произвольным радиусом. Мне нужно найти такие две точки, лежащие в окружности, через которые можно провести прямую, которая будет делить все множество точек на приблизительно равные две части.

Оригинал звучит так:
There are multitude of points(M) defined on the plane and the circle. Choose two different points from M, in such way: counts of points from M which situated in the circle and divided by line(drawn through the two points specified above) from two sides of this line, must be the same (or differ in small way).

Даже не пойму с чего начать
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.01.2014, 17:47     деление множество точек на две равные части
Посмотрите здесь:

C++ Множество точек.Найти множество треугльники
C++ Разбить файл на равные части
найти две наиболее удаленных друг от друга точки (множество точек задано на плоскости) C++
C++ на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой.
C++ Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
31.01.2014, 18:10     деление множество точек на две равные части #2
Не легкая задача, может быть такой алгоритм.
Для всех точек которые внутри окружности попробуй найти среднее арифметическое их координат, далее проведи через полученную точку и цент прямую и определи точки пересечения с окружностью. если средне арифметическое обеих координат совпадает с центром то это значит что можно брать любой диаметр: точки равномерно распределены.

Не уверен в решение проверь
some_name
Вежливость-главное оружие
 Аватар для some_name
219 / 219 / 55
Регистрация: 19.02.2013
Сообщений: 1,419
31.01.2014, 18:15     деление множество точек на две равные части #3
Если вы поняли это задание, нарисуйте в Paint, что имеется ввиду.
soundtrack
 Аватар для soundtrack
41 / 41 / 4
Регистрация: 15.12.2011
Сообщений: 131
31.01.2014, 18:26     деление множество точек на две равные части #4
Интересная задачка) сам решил задуматься над решением...

Цитата Сообщение от mustimur Посмотреть сообщение
можно брать любой диаметр
mustimur, Насколько я понял задание, окружность пересекается не диаметром, а прямой, проведённой через 2 точки внутри
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
31.01.2014, 18:33     деление множество точек на две равные части #5
Цитата Сообщение от soundtrack Посмотреть сообщение
mustimur, Насколько я понял задание, окружность пересекается не диаметром, а прямой, проведённой через 2 точки внутри
Цитата:
Цитата Сообщение от Suares Посмотреть сообщение
Мне нужно найти такие две точки, лежащие в окружности
Почему они не могут быть противоположными? Хотя в решении я не уверен, могу чушь нести

Добавлено через 30 секунд
Тьфу я не внимателен))
soundtrack
 Аватар для soundtrack
41 / 41 / 4
Регистрация: 15.12.2011
Сообщений: 131
31.01.2014, 18:36     деление множество точек на две равные части #6
mustimur, Может и я неправильно понял, конечно, но
Цитата Сообщение от Suares Посмотреть сообщение
There are multitude of points(M) defined on the plane and the circle
т.е. точки не НА окружности, а и внутри, на площади круга как дырки в решете. А прямая проходит через 2 любые из них
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
31.01.2014, 18:41     деление множество точек на две равные части #7
Вспомнил "Теоретическую механику" и понятие главных осей инерции, координаты точек - распределение массы. Найдешь гл. оси инерции и 2 точки максимально к ним близкие. Хотя тоже не уверен

Добавлено через 1 минуту
Цитата Сообщение от soundtrack Посмотреть сообщение
mustimur, Может и я неправильно понял, конечно, но
Вы правильно поняли , а у меня похоже струя в глазах
soundtrack
 Аватар для soundtrack
41 / 41 / 4
Регистрация: 15.12.2011
Сообщений: 131
31.01.2014, 18:51     деление множество точек на две равные части #8
Suares, а как у Вас с программированием? Честно, лень реализовывать код сейчас
Алгоритм как называется проверки "в лоб" таков:

Для каждого набора из пар точек А(х1, у1) и В(х2,у2) реализуете проверку всех остальных точек С(х3, у3) таким уравнением:
Код
int propertie = (х3 - х1) * (у2 - у1) - (у3 - у1) * (х2 - х1);
Если propertie = 0 - значит, точка С лежит на прямой АВ.
Если propertie < 0 - значит, точка С лежит по одну сторону от прямой.
Если propertie > 0 - значит, точка С лежит по другую сторону от прямой.
Считаете количество положительных и отрицательных значений для каждого набора проверяемых точек А и В.
В конце выбираете те из наборов, которые удовлетворяют вашему условию (количество плюсов примерно равно количеству минусов).
Наверняка есть и более оптимизированные методы, этот - метод прямого перебора

Теоретические сведения
http://habrahabr.ru/post/148325/
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
31.01.2014, 18:56     деление множество точек на две равные части #9
Класс решение, но не быстрое))
soundtrack
 Аватар для soundtrack
41 / 41 / 4
Регистрация: 15.12.2011
Сообщений: 131
31.01.2014, 18:59     деление множество точек на две равные части #10
Ну смотря сколько точек будет рассматриваться. Не думаю что он будет довольно-долгим, не так уж и много вычислений
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
31.01.2014, 19:01     деление множество точек на две равные части #11
Цитата Сообщение от soundtrack Посмотреть сообщение
Ну смотря сколько точек будет рассматриваться. Не думаю что он будет довольно-долгим, не так уж и много вычислений
Но решение самое точное выйдет в любом случае, согласен)
Suares
0 / 0 / 0
Регистрация: 28.02.2013
Сообщений: 106
31.01.2014, 20:10  [ТС]     деление множество точек на две равные части #12
Цитата Сообщение от soundtrack Посмотреть сообщение
Ну смотря сколько точек будет рассматриваться. Не думаю что он будет довольно-долгим, не так уж и много вычислений
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
#include <iostream>
#include <vector>
 
const double circleRadius = 4;
std::pair<double, double> circleCenter(5,5);
 
void initVector(std::vector< std::pair<double, double> >& v);
inline bool comparePoint(const std::pair<double, double>& p1, const std::pair<double, double>& p2, const std::pair<double, double>& p3);
inline double length(const std::pair<double, double>& p1, const std::pair<double, double>& p2);
void print(std::vector< std::pair<double, double> >& v);
void sort(std::vector< std::pair<double, double> >& v);
 
int main()
{
    std::vector< std::pair<double, double> > v;
    std::vector< std::pair<double, double> > copy;
    std::vector< std::pair<double, double> >::iterator it;
    
    //заливаем множество точек в вектор
    initVector(v);
 
    //оставляем только те точки, которые в окружность попадают. Окружность я определяю сам
    for(it = v.begin(); it != v.end(); ++it)
    {
        if(circleRadius >= length(circleCenter, *it))
        {
            copy.push_back(*it);
        }
    }
 
    //сортирую все точки которые попали в окружность по Х-координате
    sort(copy);
    //print(copy);
 
    //поделив вектор, пополам получим точку, которая лежит по середине остальных. Ну и вторую получим прибавив + 1 к середине вектора, можно и - 1 сделать :)
    //т. е. я поделил по вертикали множество точек!
    //в условии сказано что приблизительно должно быть равное количество.
    std::cout << copy[copy.size()/2 - 1].first << copy[copy.size()/2 - 1].second << std::endl;
    std::cout << copy[copy.size()/2].first << copy[copy.size()/2].second << std::endl;
 
    return 0;
}
 
void initVector(std::vector< std::pair<double, double> >& v)
{
    v.push_back(std::pair<double, double>(2,2));
    v.push_back(std::pair<double, double>(5,8));
    v.push_back(std::pair<double, double>(7,3));
    v.push_back(std::pair<double, double>(6,3));
    v.push_back(std::pair<double, double>(7,8));
    v.push_back(std::pair<double, double>(3,5));
    v.push_back(std::pair<double, double>(6,6));
    v.push_back(std::pair<double, double>(10,10));
}
 
bool comparePoint(const std::pair<double, double>& p1, const std::pair<double, double>& c, const std::pair<double, double>& p2)
{
    return ((c.first - p1.first)*(p2.second - c.second) - (p2.first - c.first)*(c.second - p1.second)) == 0;
}
 
double length(const std::pair<double, double>& p1, const std::pair<double, double>& p2)
{
    return sqrt((p2.first - p1.first)*(p2.first - p1.first) + (p2.second - p1.second)*(p2.second - p1.second));
}
 
void print(std::vector< std::pair<double, double> >& v)
{
    std::vector< std::pair<double, double> >::iterator it;
    for(it = v.begin(); it != v.end(); ++it)
    {
        std::cout << '[' << it->first << ',' << it->second << ']' << std::endl;
    }
}
 
void sort(std::vector< std::pair<double, double> >& v)
{
    for ( int i = 0; i < v.size(); i++ )
        for ( int j = 1; j < v.size(); j++ )
            if ( v[j].first < v[j-1].first )
                std::swap(v[j], v[j - 1]);
}
покаместь у меня решение такое. Если есть предложения, пишите)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.01.2014, 20:54     деление множество точек на две равные части
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
jurok_85
226 / 209 / 70
Регистрация: 21.02.2013
Сообщений: 494
31.01.2014, 20:54     деление множество точек на две равные части #13
тоже заинтересовала задачка, вот как попробывал реализовать
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
#include <iostream>
#include <cmath>
#define M 1000
#define R 100
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;
struct coordinati{
    float a;
    float b;
    void set_coord(float& x, float& y)
    {
        a = x;
        b = y;
    }
};
int main()
{
        coordinati coord;
        vector<coordinati> vec;
    srand(time(NULL));
    int i = 0;
 
    float x, y;
    while(i != M)
    {
        x = (rand()%(R *2)) - R;
        y = (rand()%(R *2)) - R;
 
        if(sqrt(x*x + y*y) <= R)
        {
            coord.set_coord(x,y);
            vec.push_back(coord);
        }
        i++;
    }
    for(vector<coordinati>::size_type i = 0; i != vec.size(); i++)
    {
                for(vector<coordinati>::size_type j = 0; j != vec.size(); j++)
                {
                    if(vec[i].a == (- vec[j].a)&& vec[i].b == -(vec[j].b))
                    cout << "Cherez tochku a[" << vec[i].a <<"][" << vec[i].b << "]" <<
                    " i tuchku b[" << vec[j].a <<"][" << vec[j].b <<"]" <<
                    "mozhno razdelitj krug popolam" << endl;
 
                }
    }
return 0;
}
Добавлено через 20 минут
а не немного неправильно задание понял
Yandex
Объявления
31.01.2014, 20:54     деление множество точек на две равные части
Ответ Создать тему
Опции темы

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