Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 19.06.2016
Сообщений: 33
1

Выбрать три разные точки А, В, С так, чтобы внутри треугольника АВС содержалось максимальное количество точек

26.03.2017, 14:10. Показов 1066. Ответов 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
64
65
66
67
#include <iostream.h>
 
class Point
{
    private:
                int *a, n, p, v ;
                double x, y, z;
                int (*points)[2], (*kt)[2];
    public:
                Point () {kt = new int [3][2] ; points = NULL; }
                ~Point() {delete [] points; points = NULL; delete [] kt ; kt = NULL;}
                double X(){return x;}
                double Y(){return y;}
                Point(const double X, const double Y): x(X), y(Y){}
                void vvod();
                void vyvod();
};
 
class Triangle
{
    private:
              Point vert[3];
              double a, b, c;
    public:
              void resh();
              Triangle(const Point &p1, const Point &p2, const Point &p3);
};
 
    void Point::vvod()
      {
            cout << "Задайте количество точек: ";
            cin >> p;
            points=new int [n][2];
            cout << "Задайте координаты точек" << endl;
            for (int i=0; i<p; i++)
            {
                cout << "Задайте координату x: " << (i+1) << "точки: ";
                cin >> points [i][0];
                cout << "Задайте координату y: " << (i+1) << "точки: ";
                cin >> points [i][1];
        }
    };
 
    void Triangle::resh()
      {
          vert[0] = a;
          vert[1] = b;
          vert[2] = c;
      }
          {
              a = (vert[0].X() - p.X())*(vert[1].Y() - vert[0].Y())-(vert[1].X() - vert[0].X())*(vert[0].Y() - p.Y());
              b = (vert[1].X() - p.X())*(vert[2].Y() - vert[1].Y())-(vert[2].X() - vert[1].X())*(vert[1].Y() - p.Y());
              c = (vert[2].X() - p.X())*(vert[0].Y() - vert[2].Y())-(vert[0].X() - vert[2].X())*(vert[2].Y() - p.Y());
              if ((a >= 0 && b >= 0 && c >= 0) || (a <= 0 && b <= 0 && c <= 0))
              {
                 return true;
              }
                 return false;
          }
 
    int main(int argc, char *argv[])
    {
        Triangle t(Point(10,10), Point(20,10), Point(20,20));    //Треугольник
        Point p;         //Точка
        t == p ? cout <<"Точка принадлежит треугольнику": cout <<"Точка не принадлежит треугольнику";
        return 0;
    }
Перепробовал кучу методов, в итоге оставил вот эту часть кода.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.03.2017, 14:10
Ответы с готовыми решениями:

Выбрать из множества три разные точки так, чтобы внутри треугольника содержалось максимальное количество точек
Задача такова : Из заданного множества точек на плоскости выбрать три разные точки А В С так,...

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

Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точ
Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри...

Выбрать 3 разные точки A,B,C так, чтобы внутри треугольника ABC содержалось макс. количество точек
Из заданного множества точек на плоскости выбрать 3 разные точки A,B,C так, чтобы внутри...

3
Эксперт C
25592 / 15962 / 3418
Регистрация: 24.12.2010
Сообщений: 34,913
26.03.2017, 22:48 2
yexela, Теги кода умеете ставить?
0
0 / 0 / 0
Регистрация: 19.06.2016
Сообщений: 33
29.03.2017, 07:47  [ТС] 3
Умею
0
С чаем беда...
Эксперт CЭксперт С++
8652 / 4322 / 1190
Регистрация: 18.10.2014
Сообщений: 9,395
29.03.2017, 09:47 4
Понятно, что все три искомые точки будут вершинами выпуклой оболочки исходного набора точек. Возможно, что стоит начать с поиска выпуклой оболочки. А вот какое остроумное решение придумать тогда, когда выпуклая оболочка уже построена - надо думать.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.03.2017, 09:47

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

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

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

Даны два множества точек на плоскости. Выбрать три точки так, чтобы треугольник с вершинами в этих точках содержал равное количество точек
Даны два множества точек на плоскости. Из первого множества выбрать три различные точки так, чтобы...

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

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

Выбрать среди точек три так, чтобы у полученного треугольника площадь была максимальной
Задача F. Треугольник Вам задаются N точек на плоскости. Нужно выбрать среди них три так, чтобы у...


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

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

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