Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.79/29: Рейтинг темы: голосов - 29, средняя оценка - 4.79
0 / 0 / 0
Регистрация: 28.02.2013
Сообщений: 106

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

31.01.2014, 17:47. Показов 5611. Ответов 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
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
31.01.2014, 17:47
Ответы с готовыми решениями:

Разбить массив на две равные части (или приблизительно равные)
Задали задание. Нужно разбить одномерный массив на две почти равные части(если на равные не получается). Написал программу, однако...

Деление массива на равные части
Здравствуйте! Есть задание: "написать функцию, которая проверяет возможно ли поделить массива на, как минимум, две равные части (имеющие...

Деление массива на равные части (JS)
Как можно в JS поделить массив на равные интервалы? Например, на 4 равных интервала. for (var i = 0; i < 4; i++) { ...

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

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

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

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

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

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

Теоретические сведения
http://habrahabr.ru/post/148325/
2
320 / 225 / 74
Регистрация: 22.11.2013
Сообщений: 867
Записей в блоге: 1
31.01.2014, 18:56
Класс решение, но не быстрое))
0
 Аватар для soundtrack
42 / 42 / 12
Регистрация: 15.12.2011
Сообщений: 131
31.01.2014, 18:59
Ну смотря сколько точек будет рассматриваться. Не думаю что он будет довольно-долгим, не так уж и много вычислений
0
320 / 225 / 74
Регистрация: 22.11.2013
Сообщений: 867
Записей в блоге: 1
31.01.2014, 19:01
Цитата Сообщение от soundtrack Посмотреть сообщение
Ну смотря сколько точек будет рассматриваться. Не думаю что он будет довольно-долгим, не так уж и много вычислений
Но решение самое точное выйдет в любом случае, согласен)
0
0 / 0 / 0
Регистрация: 28.02.2013
Сообщений: 106
31.01.2014, 20:10  [ТС]
Цитата Сообщение от 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
365 / 321 / 219
Регистрация: 21.02.2013
Сообщений: 756
31.01.2014, 20:54
тоже заинтересовала задачка, вот как попробывал реализовать
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
31.01.2014, 20:54
Помогаю со студенческими работами здесь

Деление дуги на равные части. Измерение этих частей
Автокад 2010. Задача максимум. Поделить дугу на равные части по условию, что размер этих частей не должен быть более известного значения,...

Дано множество точек на плоскости. Сколько точек не принадлежит прямой, проходящей через две первые точки?
Доброго вечера! Подскажите, пожалуйста, по следующей задаче: Дано множество точек на плоскости. Сколько точек не принадлежит прямой,...

Задача про деление массива на три равные по сумме части,не включая точки деления
Добрый день!Выкладываю описание задания на английском языке.В принципе алгоритм для меня ясен,но он имеет сложность больше,чем Q(N).А что...

Разделение массива на две равные части
Заполняю массив размером 20 рандомными числами от 0 до 200. Надо разделить этот массив на две равные части. И эти части занести в массивы...

Дана строка. Необходимо разделить ее на две равные части
Дана строка. Необходимо разделить ее на две равные части (если длина строки — четная, а если длина строки нечетная, то длина первой части...


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru