Среди треугольников с вершинами в заданном множестве точек на плоскости

@Kuzichka · Регистрация: 16.05.2012

Студворк — интернет-сервис помощи студентам

Среди треугольников с вершинами в заданном множестве точек на плоскости указать такой, стороны которого содержат максимально число точек заданного множества.

Как я поняла сначала создать два массива координаты X и Y
Потом перебираем точки
Первый цикл: что бы тч не лежали на одной прямой...
А дальше... что??(

@VaJI · 25.03.2013, 15:59

Kuzichka, можно один двумерный) или же массив структур.
1. определяем и заполняем массив точек.
2. начинаем цикл по 3 точкам.
2.1 начинаем цикл по первой точки
2.2 начинаем цикл по второй точке в тоже время параметр цикла не должен брать первую выбранную точку.
2.3 тоже 2.2 только для третьей( в общем нужно добиться чтобы точки были разными)
3. проверка на "треугольность" точек(чтоб не лежали на одной прямой)
4. далее задаем по точкам некую фигуру ограниченная 3мя функциями(прямыми y = ax + b)
5. далее еще один цикл который перебирает все точки и ищет те, при которых выполняется неравенство (y <> ax + b)
6. если такое кол-во точек больше прежнего, то соответственно у нас новый максимум вхождений.

вот еще про треугольник:

Сообщение от Somebody

5. Про треугольник.
Математическая часть - векторное и псевдоскалярное произведение.
Реализация - считаются произведения (1,2,3 - вершины треугольника, 0 - точка):
(x1-x0)*(y2-y1)-(x2-x1)*(y1-y0)
(x2-x0)*(y3-y2)-(x3-x2)*(y2-y0)
(x3-x0)*(y1-y3)-(x1-x3)*(y3-y0)
Если они одинакового знака, то точка внутри треугольника, если что-то из этого - ноль, то точка лежит на стороне, иначе точка вне треугольника.

@Kuzichka · 25.03.2013, 16:10 **[ТС]**

Спасибо)) Лучше остаться с двумя массивами, так проще как то...) Осталось реализовать)

Добавлено через 5 минут

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
#include <iostream>
#include <ctime>
#include <cmath>
 
using namespace std;
 
void create(double *a,double *b,int N) //создание массива
{
for (int i=0;i<N;i++)
{
     a[i]=i;
     b[i]=i+N;
}
}
 
 
void get(double *a,double *b,int N) //Поиск трех злостных точек
{
    tpoint T1,T2,T3; //три точки
 
 
    for (int i=0;i<N;i++)  //Анализ всех комбинаций для построения треугольиков
        for (int j=i+1;j<N;j++)
            for (int k=j+1;k<N;k++)
    {

Начало правильное?? )) Я первый раз пишу на на С++ будьте снисходительны))

@VaJI · 25.03.2013, 16:53

Сообщение от Kuzichka

C++
1
2
3
4
5
6
7
8
void create(double *a,double *b,int N) //создание массива
{
for (int i=0;i<N;i++)
{
a[i]=i;
b[i]=i+N;
}
}

вы создаете указатели на переменную а не массив. Если хотите создать динамический массив познакомьтесь с функцией operator new(). А лучше хотя бы какой нибудь курс прочтите, что то типа C++ за 21 день.
Слишком сложно для первой задачи

Добавлено через 2 минуты
и еще что вы хотите с помощью функции get()? поиск 3 точек? а зачем их искать? и начните с главной функции main опишите какие функции хотите видеть в своей программе.

@Kuzichka · 25.03.2013, 16:56 **[ТС]**

я думала основную часть так сделать..

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void main()
{
system("CLS");
double *Arr1,*Arr2;
int N=9;
Arr1=new double[N];
Arr2=new double[N];
 
create(Arr1,Arr2,N); //Создание массива из N элементов
show(Arr1,Arr2,N); //отображение массива на экране
get(Arr1,Arr2,N); //Поис злых точек
 
}

Добавлено через 1 минуту
но я уже запуталась(

@VaJI · 25.03.2013, 17:14

Сообщение от Kuzichka

create(Arr1,Arr2,N); //Создание массива из N элементов

вы его уже создали вот этими строками:

Сообщение от Kuzichka

int N=9;
Arr1=new double[N];
Arr2=new double[N];

а здесь вы его инициализируете:

Сообщение от Kuzichka

void create(double *a,double *b,int N)
{
for (int i=0;i<N;i++)
{
a[i]=i;
b[i]=i+N;
}
}

Добавлено через 44 секунды
но это придирки) пока что все хорошо)

@Kuzichka · 25.03.2013, 17:18 **[ТС]**

Дальше я планировала сделать поиск точек с помощью get, но вы сказали
" поиск 3 точек? а зачем их искать?" ... и я не знаю, что делать дальше(

@VaJI · 25.03.2013, 17:29

ну смотрите, функцию get() тоже желательно разбить на подзадачи:
1. проверка точек на "треугольность"
2. подсчет точек, а точнее сколько вхождений в данную фигуру при нынешних точках.. кстати проверить точка входит в треугольник из трех точек можно вынести тоже в отдельную функцию.
на подсчет точек тоже необходим массив.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере 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-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@Kuzichka 0 / 0 / 0 Регистрация: 16.05.2012 Сообщений: 32

	Среди треугольников с вершинами в заданном множестве точек на плоскости 25.03.2013, 14:53. Показов 5598. Ответов 7 Метки нет (Все метки) Среди треугольников с вершинами в заданном множестве точек на плоскости указать такой, стороны которого содержат максимально число точек заданного множества. Как я поняла сначала создать два массива координаты X и Y Потом перебираем точки Первый цикл: что бы тч не лежали на одной прямой... А дальше... что??( 0

@Kuzichka 0 / 0 / 0 Регистрация: 16.05.2012 Сообщений: 32
	25.03.2013, 17:18 [ТС]
	Дальше я планировала сделать поиск точек с помощью get, но вы сказали " поиск 3 точек? а зачем их искать?" ... и я не знаю, что делать дальше( 0

@VaJI 7 / 5 / 5 Регистрация: 24.03.2013 Сообщений: 40
	25.03.2013, 17:29
	ну смотрите, функцию get() тоже желательно разбить на подзадачи: 1. проверка точек на "треугольность" 2. подсчет точек, а точнее сколько вхождений в данную фигуру при нынешних точках.. кстати проверить точка входит в треугольник из трех точек можно вынести тоже в отдельную функцию. на подсчет точек тоже необходим массив. 0