Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.68/25: Рейтинг темы: голосов - 25, средняя оценка - 4.68
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69

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

17.07.2013, 22:11. Показов 5303. Ответов 29
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте.
При реализации задачи я столкнулся с некоторой трудностью (ну, по крайней мере для меня).
Собственно, текст задачи:
Даны два множества точек на плоскости. Выбрать три различные точки первого множества так, чтобы треугольник с вершинами в этих точках накрывал все точки второго множества и имел минимальную площадь.

Небольшое лирическое отступление. Тут я такую задачу встречал много раз и все, за исключением одной (написанная на паскале) были проигнорированны и попросту забыты - утонули в дебрях других тем. Кто знает, не отвечали потому, что не отвечали, либо не было желания объяснять что и как, либо, что вероятнее всего, не написали из-за того, что человек, который просил решения, просто "скопипастит" задачу и все... и уход в затемнение, короче - просто сдаст и забудет... НО это всего лишь догадки, не более того. А чего я хочу? Бляха, просто понять эту задачу, нет, смысл я ее понял и как реализовывать примерно знаю, НО есть некотарая проблема - не все места я знаю как написать.
Ну да ладно.
Вот код:
Java
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
public class Point 
{
    private double x; //koordinati tochek
    private double y; //koordinati tochek
    public Point(double x, double y)
    {
        this.x = x;
        this.y = y; 
    }
    public void setX(double x)
    {
        this.x = x;
    }
    public double getX(double x)
    {
        return x;
    }
    public void setY(double y)
    {
        this.y = y;
    }
    public double getY(double y)
    {
        return y;
    }   
    public String toString()
    {
        return "(" + x + "||" + y + ")";
    }
}
Что я тут делаю. Описываю точки множества, чтобы в дальнейшем с ними "работать".
Вот второй класс (заведомо неправильный, а для человека знающего наверное покажется, что код писал умалишенный)
Ниже код:
Java
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
public class Triangle 
{
    private double point_a; // wershina A treugolnika
    private double point_b; // wershina B treugolnika
    private double point_c; // wershina C treugolnika
    private double x; // koordinati tochek
    private double y; // koordinati tochek
    public Triangle(double x, double y)
    {
        this.x = x;
        this.y = y; 
    }
    public void setX(double x)
    {
        this.x = x;
    }
    public double getX(double x)
    {
        return x;
    }
    public void setY(double y)
    {
        this.y = y;
    }
    public double getY(double y)
    {
        return y;
    }
    public void setPoint_a(double x, double y) 
    {
        this.point_a = point_a;
    }
    public double getPoint_a() 
    {
        return point_a;
    }
    public void setPoint_b(double x, double y) 
    {
        this.point_b = point_b;
    }
    public double getPoint_b() 
    {
        return point_b;
    }
    public void setPoint_c(double x, double y) 
    {
        this.point_c = point_c;
    }
    public double getPoint_c() 
    {
        return point_c;
    }
    public String toString()
    {
        return "(" + x + "||" + y + ")";
    }
 
    public double area(Triangle x, Triangle y)
    {
        double result = 0;
        double p = (point_a + point_b + point_c)/2;
        result = Math.sqrt(p*(p-point_a)*(p-point_b)*(p-point_c)); //wichislenie S treugolnika - formula Gerona (esli wse werno naiti i wiwesti w rezultate etu samuy plochad S(w otdelnom metode))
        //Dopisat nahojdenie minimalnoi plochadi S treugolnika(est nekotorie woprosi kak eto realizowat)
        return result;  
    }
    public boolean pointInTriangle(Triangle x, Triangle y) //nakriwaet treugolnik tochki mnojestwa ili net nakriwaet - wiwesti koordinati treugolnika - true (realizowat wiwod koordinat w otdelnom metode) ne nakriwaet - false
    {
        if(pointInTriangle(x, y) < area.pointInTriangle(point_a, point_b, point_c); //kak opisat, chto tochki mnojestwa wnutri treugolnika?
        {
            
        }
    }
 
 
}
Что я тут делаю. Гхм, пытаюсь описать эти самые треугольники (комментарии подробнее описываю ход мыслей).
НО, один очень хороший человек посоветовал мне следующее: "почему бы не описать три вершины треугольника как три объекта типа Point."

Вот мой вопрос. Как описать эти вершины, как мне говорят это сделать? Собственно все.

З.Ы. еще раз повторюсь мне не надо решать всю задачу помогите мне вот в этой загвостке, а дальше я постараюсь сам, ну если будут какие трудности - буду обращаться за помощью, мне главное - ПОНЯТЬ.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
17.07.2013, 22:11
Ответы с готовыми решениями:

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

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

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

29
352 / 162 / 20
Регистрация: 22.12.2011
Сообщений: 352
24.07.2013, 14:42
Студворк — интернет-сервис помощи студентам
iiyuijkhgfjf, чего хоть говорит то? На какой строчке ругается?
И кстати, зачем в строчках 79 и 90 стоят скобки?

Не по теме:

Еще раз рекомендую освоить IDE

0
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
24.07.2013, 14:52  [ТС]
Цитата Сообщение от Sakralbar Посмотреть сообщение
И кстати, зачем в строчках 79 и 90 стоят скобки?
Моя оплошность, исправил.
Цитата Сообщение от Sakralbar Посмотреть сообщение
чего хоть говорит то? На какой строчке ругается?
Все зависит от ситуации и что я напишу в return.
По идее я хотел сделать следующее:
треугольник найден - вывод минимальной площади areaMin и вывод индексов точек.
Как то так должно быть (" минимальная площадь", "индексы точек" , areaMin, A, B, C)
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12848 / 7597 / 1766
Регистрация: 25.07.2009
Сообщений: 13,985
24.07.2013, 15:31
Цитата Сообщение от iiyuijkhgfjf Посмотреть сообщение
треугольник найден - вывод минимальной площади areaMin и вывод индексов точек.
У отдельно взятого треугольника минимальная площадь - она же максимальная. Суть в том, что из трёх точек взятых из массива точек для треугольников:
а) вообще не получится треугольник
б) получится треугольник не накрывающий все точки
в) получится треугольник накрывающий все точки
Вот из последних (а их может получиться несколько) нужно отобрать тот, у которого площадь минимальная...
0
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
24.07.2013, 17:02  [ТС]
easybudda, я все это так и делаю.

Я понять не могу, как мне полученный треугольник, а именно результат, вернуть.

Добавлено через 2 минуты
Буду благодарен за если будут идеи/предложения/часть кода как образец.
Просто обидно - подкосился на финишной прямой.
По сути мне нужно теперь вернуть треугольник по трем уже найденым точкам. (как?).
0
ɐwʎ ɔ vǝmоɔ dиw ɐʚонɔ
 Аватар для tankomaz
443 / 442 / 100
Регистрация: 14.10.2012
Сообщений: 1,146
Записей в блоге: 9
24.07.2013, 17:02
Цитата Сообщение от iiyuijkhgfjf Посмотреть сообщение
easybudda, я все это так и делаю.

Я понять не могу, как мне полученный треугольник, а именно результат, вернуть.

Добавлено через 2 минуты
Буду благодарен за если будут идеи/предложения/часть кода как образец.
Просто обидно - подкосился на финишной прямой.
По сути мне нужно теперь вернуть треугольник по трем уже найденым точкам. (как?).
можно как массив из точек (ссылку на массив)
0
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
24.07.2013, 17:04  [ТС]
Можно, пожалуйста пример - тут нужен мозговой штурм...
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12848 / 7597 / 1766
Регистрация: 25.07.2009
Сообщений: 13,985
24.07.2013, 17:08
iiyuijkhgfjf, у меня в примере подходящие треугольники в set складываются, а в нём сами по площади сортируются. В конце процесса, если set не пустой, то первый в нём треугольник и есть нужный.
0
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
25.07.2013, 18:39  [ТС]
easybudda, а можете указать номер строки, чтобы не ошибиться.

Добавлено через 17 минут
Или даже так:
См. комментарий в конце кода
Java
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
public class Triangle 
{
    Point pointA;
    Point pointB; 
    Point pointC;
    //Triangle triangle;
    public Triangle(Point pointA, Point pointB, Point pointC)
    {
        this.pointA = pointA;
        this.pointB = pointB;
        this.pointC = pointC;   
        //this.triangle = triangle;
    }
    public Point getPointA() 
    {
        return pointA;
    }
    public void setPointA(Point pointA) 
    {
        this.pointA = pointA;
    }
    public Point getPointB() 
    {
        return pointB;
    }
    public void setPointB(Point pointB) 
    {
        this.pointB = pointB;
    }
    public Point getPointC() 
    {
        return pointC;
    }
    public void setPointC(Point pointC) 
    {
        this.pointC = pointC;
    }   
    public double area()
    {
        return Math.abs((pointB.x - pointA.x)*(pointC.y - pointA.y) - (pointC.x - pointA.x)*(pointB.y - pointA.y))/2;
    }
    public boolean inTriangle(Point point)
    {
        double e = 0.001;
        double S1;
        double S2;
        double S3;
        double S4;
        S1 = area();
        S2 = area();
        S3 = area();
        S4 = area();
        double diff = Math.abs(S1 - (S2 + S3 + S4));
        if(diff < e)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    public Triangle minTriangle(Point[] array)
    {
        //Triangle triangle;
        Point[] arrayA = new Point[15]; // первое множество точек
        Point[] arrayB = new Point[15]; // второе множество точек
        double areaMin = 0;
        int A; // индекс точки
        int B; // индекс точки
        int C; // индекс точки
        for(int i = 0; i<(arrayA.length-2); i++)
        {
            for(int j = i+1; j<(arrayA.length-1); j++)
            {
                for(int k = j+1; k<(arrayA.length); k++)
                {
                    Triangle triangle = new Triangle(arrayA[i], arrayA[j], arrayA[k]);
                    //{
                        for(int m = 0; m<arrayB.length; m++)
                        {
                            if(triangle.inTriangle(arrayB[m]) && (areaMin == 0 || (triangle.area() <= areaMin)))
                            {
                                areaMin = triangle.area();
                                A = i;
                                B = j;
                                C = k;
                            }
                        }
                    //}
                }
            }
        }
        if(areaMin < 0)
        {
            return null;
            
        }
        else
        {
            return //что сдесь писать? по идее должен быть треугольник и его индексы точек как это написать - без понятия; 
            
        }
    }
}
Вот, в комментарии суть моей проблемы.

Добавлено через 20 часов 54 минуты
Здравствуйте.
ТОВАРИЩИ, помогите вернуть в методе minTriangle треугольник, они мне уже снятся...
Java
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
public class Triangle 
{
    Point pointA;
    Point pointB; 
    Point pointC;
    //Triangle triangle;
    public Triangle(Point pointA, Point pointB, Point pointC)
    {
        this.pointA = pointA;
        this.pointB = pointB;
        this.pointC = pointC;   
        //this.triangle = triangle;
    }
    public Point getPointA() 
    {
        return pointA;
    }
    public void setPointA(Point pointA) 
    {
        this.pointA = pointA;
    }
    public Point getPointB() 
    {
        return pointB;
    }
    public void setPointB(Point pointB) 
    {
        this.pointB = pointB;
    }
    public Point getPointC() 
    {
        return pointC;
    }
    public void setPointC(Point pointC) 
    {
        this.pointC = pointC;
    }   
    public double area()
    {
        return Math.abs((pointB.x - pointA.x)*(pointC.y - pointA.y) - (pointC.x - pointA.x)*(pointB.y - pointA.y))/2;
    }
    public boolean inTriangle(Point point)
    {
        double d1 = (pointA.getX() - point.getX()) * (pointB.getY() - pointA.getY()) - (pointB.getX() - pointA.getX()) * (pointA.getY() - point.getY());
        double d2 = (pointB.getX() - point.getX()) * (pointC.getY() - pointB.getY()) - (pointC.getX() - pointB.getX()) * (pointB.getY() - point.getY());
        double d3 = (pointC.getX() - point.getX()) * (pointA.getY() - pointC.getY()) - (pointA.getX() - pointC.getX()) * (pointC.getY() - point.getY());
        return ( ( d1 * d2 > 0 ) && ( d2 * d3 > 0 ) );
    }
    public static double minTriangle(Point[] array)
    {
        //Triangle triangle;
        Point[] arrayA = {new Point(0, 0),
                   new Point(0, 10),
                   new Point(10, 0),
                   new Point(0, 5),
                   new Point(5, 0),
                   new Point(3, 3),}; 
        Point[] arrayB = {new Point(1, 2),
                new Point(2, 3),
                new Point(1, 3),}; 
        //Point[] arrayA = new Point[15]; // первое множество точек
        //Point[] arrayB = new Point[15]; // второе множество точек
        double areaMin = 0;
        int A = 0; // индекс точки
        int B = 0; // индекс точки
        int C = 0; // индекс точки
        for(int i = 0; i<(arrayA.length-2); i++)
        {
            for(int j = i+1; j<(arrayA.length-1); j++)
            {
                for(int k = j+1; k<(arrayA.length); k++)
                {
                    Triangle triangle = new Triangle(arrayA[i], arrayA[j], arrayA[k]);
                    //{
                        for(int m = 0; m<arrayB.length; m++)
                        {
                            if(triangle.inTriangle(arrayB[m]) && (areaMin == 0 || (triangle.area() <= areaMin)))
                            {
                                areaMin = triangle.area();
                                A = i;
                                B = j;
                                C = k;
                            }
                        }
                    //}
                }
            }
        }
        if(areaMin < 0)
        {
            System.out.println("It isn't found points"); // точек не найдено
            
        }
        else
        {
            System.out.println("Point A: " +A);
            System.out.println("Point B: " +B);
            System.out.println("Point C: " +C); 
            System.out.println("Minimum area: " +areaMin);
            
        }
        return 0;
        
    }
}
0
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
26.07.2013, 01:42
Java
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
public class FindTriangle {
    private static class Point {
        public final double x, y;
 
        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
 
        @Override
        public String toString() {
            return "(" + x + ", " + y + ")";
        }
    }
 
    private static class Triangle {
        public final Point a, b, c;
 
        private Triangle(Point a, Point b, Point c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
 
        public double area() {
            return 0.5 * Math.abs((b.x - a.x) * (c.y - a.y) -
                    (b.y - a.y) * (c.x - a.x));
        }
 
        public boolean contains(Point p) {
            double a1 = new Triangle(p, b, c).area();
            double a2 = new Triangle(a, p, c).area();
            double a3 = new Triangle(a, b, p).area();
            return Math.abs(area() - a1 - a2 - a3) < 1e-4;
        }
 
        public boolean containsAll(Point... points) {
            for (Point point : points) {
                if (!contains(point))
                    return false;
            }
            return true;
        }
 
        @Override
        public String toString() {
            return "Triangle(" + a + "," + b + "," + c + ")";
        }
    }
 
    private static Triangle findTriangle(Point[] first, Point[] second) {
        if (first.length < 3)
            return null;
        Triangle result = null;
        double minArea = -1;
        for (int i = 0; i < first.length; i++) {
            for (int j = i + 1; j < first.length; j++)
                for (int k = j + 1; k < first.length; k++) {
                    Triangle triangle = new Triangle(first[i], first[j], first[k]);
                    double area = triangle.area();
                    if (triangle.containsAll(second) && (minArea < 0 || area < minArea)) {
                        result = triangle;
                        minArea = area;
                    }
                }
        }
        return result;
    }
 
    public static void main(String[] args) {
        Point[] first = new Point[]{
                new Point(0, 0), new Point(0, 10),
                new Point(10, 0), new Point(0, 5),
                new Point(5, 0), new Point(3, 3)
        };
        Point[] second = new Point[]{
                new Point(1, 2), new Point(2, 3), new Point(1, 3)
        };
        System.out.println(findTriangle(first, second));
    }
}
2
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
26.07.2013, 13:36  [ТС]
Здравствуйте.
С задачей разобрался всем ОГРОМНОЕ спасибо, за помощь.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
26.07.2013, 13:36

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru