Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Suares
0 / 0 / 0
Регистрация: 28.02.2013
Сообщений: 106
#1

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

31.01.2014, 17:47. Просмотров 1126. Ответов 12
Метки нет (Все метки)

Есть у меня множество точек и окружность с произвольным радиусом. Мне нужно найти такие две точки, лежащие в окружности, через которые можно провести прямую, которая будет делить все множество точек на приблизительно равные две части.

Оригинал звучит так:
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).

Даже не пойму с чего начать
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.01.2014, 17:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос деление множество точек на две равные части (C++):

найти две наиболее удаленных друг от друга точки (множество точек задано на плоскости) - C++
Помогите, пожалуйста, написать программу на С++, используя структуру point для хранения координат точки: следует найти две наиболее...

Круг, множество точек, прямая проходящая через две точки и через центр круга - C++
плиз хелп. Нужно вывести координаты двух точек. #include <stdio.h> #include <math.h> #include <random> #include <ctime> using...

На плоскости заданы множество точек А и множество прямых В (каждая прямая задается значениями коэффициентов ур - C++
На плоскости заданы множество точек А и множество прямых В (каждая прямая задается значениями коэффициентов уравнения). Найти две такие...

На плоскости заданы множество точек А и множество прямых B - C++
На плоскости заданы множество точек А и множество прямых B. Найти две такие различные точки из А, чтобы проходящая через них прямая была...

Дано множество точек на плоскости, заданных полярными координатами. Получить декартовы координаты этих точек - C++
Получилось сделать для координаты одной точки, а как сделать для множества точек, через цикл или массив? #include <stdio.h> #include...

Множество точек.Найти множество треугльники - C++
ДАно 3n точек на плоскости , причем не какие три не лежат на одной прямой. Построить множество треугольников с вершинами в этих точках так...

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

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

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

Добавлено через 30 секунд
Тьфу я не внимателен))
1
soundtrack
42 / 42 / 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 любые из них
1
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
31.01.2014, 18:41 #7
Вспомнил "Теоретическую механику" и понятие главных осей инерции, координаты точек - распределение массы. Найдешь гл. оси инерции и 2 точки максимально к ним близкие. Хотя тоже не уверен

Добавлено через 1 минуту
Цитата Сообщение от soundtrack Посмотреть сообщение
mustimur, Может и я неправильно понял, конечно, но
Вы правильно поняли , а у меня похоже струя в глазах
0
soundtrack
42 / 42 / 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/
2
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
31.01.2014, 18:56 #9
Класс решение, но не быстрое))
0
soundtrack
42 / 42 / 4
Регистрация: 15.12.2011
Сообщений: 131
31.01.2014, 18:59 #10
Ну смотря сколько точек будет рассматриваться. Не думаю что он будет довольно-долгим, не так уж и много вычислений
0
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
31.01.2014, 19:01 #11
Цитата Сообщение от soundtrack Посмотреть сообщение
Ну смотря сколько точек будет рассматриваться. Не думаю что он будет довольно-долгим, не так уж и много вычислений
Но решение самое точное выйдет в любом случае, согласен)
0
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]);
}
покаместь у меня решение такое. Если есть предложения, пишите)
0
jurok_85
241 / 225 / 78
Регистрация: 21.02.2013
Сообщений: 520
Завершенные тесты: 1
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 минут
а не немного неправильно задание понял
0
31.01.2014, 20:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.01.2014, 20:54
Привет! Вот еще темы с ответами:

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

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

Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества - C++
Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого...

Разбить файл на равные части - C++
Подскажите пожалуйста, как разбить файл с содержимым, средствами с++ на равные части(последний кусок может быть меньше) я нашел на...


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

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

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