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

@iiyuijkhgfjf · Регистрация: 15.03.2013

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

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

Небольшое лирическое отступление. Тут я такую задачу встречал много раз и все, за исключением одной (написанная на паскале) были проигнорированны и попросту забыты - утонули в дебрях других тем. Кто знает, не отвечали потому, что не отвечали, либо не было желания объяснять что и как, либо, что вероятнее всего, не написали из-за того, что человек, который просил решения, просто "скопипастит" задачу и все... и уход в затемнение, короче - просто сдаст и забудет... НО это всего лишь догадки, не более того. А чего я хочу? Бляха, просто понять эту задачу, нет, смысл я ее понял и как реализовывать примерно знаю, НО есть некотарая проблема - не все места я знаю как написать.
Ну да ладно.
Вот код:

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."

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

З.Ы. еще раз повторюсь мне не надо решать всю задачу помогите мне вот в этой загвостке, а дальше я постараюсь сам, ну если будут какие трудности - буду обращаться за помощью, мне главное - ПОНЯТЬ.

@tankomaz · 17.07.2013, 23:41

Java
1
2
3
4
5
Point p1 = new Point(...);
Point p2 = new Point(...);
Point p3 = new Point(...);
 
Triagle t1 = new Triagle(p1, p2, p3);

создаете класс Triagle с конструктором на три Point'a. Вы это хотели уточнить? (композиция называется)
или вы хотите чтобы мы помогли именно с методами определения плоскостей и координат?

"как-то так" (с)

Java
1
2
3
4
5
6
7
8
9
public class Triangle 
{
    Point p1 = null;
    Point p2 = null;
    Point p3 = null;
    
public Triangle (Point p1, Point p2, Point p3) {
        this.p1 = p1;
        .....

@iiyuijkhgfjf · 18.07.2013, 20:17 **[ТС]**

Здравствуйте.
Да, именно второй вариант, а именно "мы помогли именно с методами определения плоскостей и координат" вот в этом загвостка.

Добавлено через 1 минуту
Да и первый, можно, пожалуйста "разжевать".

Добавлено через 20 часов 12 минут
День добрый.
Вот, подкорректированный код.
Собственно я разбил свою задачу на подзадачи:
1. Нужно написать вычисление площади треугольника.
2. Проверить, находятся ли точки множества внутри треугольника.
3. Найти треугольник минимальной площади, который накрывает все точки множества.
4. Вывести полученный результат на экран.

С первыми двумя пунктами вроде бы как "расквитался" (проверьте, авось).
Вот решил перейти на 3-й и... вобщем нужно объяснение - как сделать.
Ниже вот что наклепал:

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
public class Point 
{
    double x; //koordinati tochek
    double y; //koordinati tochek
    public Point(double x, double y)
    {
        this.x = x;
        this.setY(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 + "||" + getY() + ")";
    }
    double getY() {
        return 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
public class Triangle2 
{
    Point pointA;
    Point pointB; 
    Point pointC;
    public Triangle2(Point pointA, Point pointB, Point pointC)
    {
        this.pointA = pointA;
        this.pointB = pointB;
        this.pointC = pointC;    
    }
    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(Point pointA, Point pointB, Point pointC)
    {
        double result = 0;
        //Math.abs((pointB.x - pointA.x)*(pointC.y - pointA.y) - (pointC.x - pointA.x)*(pointB.y - pointA.y))/2;
        result = Math.abs((pointB.x - pointA.x)*(pointC.y - pointA.y) - (pointC.x - pointA.x)*(pointB.y - pointA.y))/2;
        return result;
    }
    public boolean inTriangle(Point pointA, Point pointB, Point pointC, Point point)
    {
        double e = 0.001;
        double S1;
        double S2;
        double S3;
        double S4;
        S1 = area(pointA, pointB, pointC);
        S2 = area(pointA, pointB, point);
        S3 = area(pointA, pointC, point);
        S4 = area(pointC, pointB, point);
        double diff = Math.abs(S1 - (S2 + S3 + S4));
        if(diff < e)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}

@kamre · 21.07.2013, 22:27

До чего же много в Java бойлерплейт кода по сравнению с:

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
object FindTriangle extends App {
  import language.implicitConversions
  case class Point(x: Double, y: Double)
  case class Triangle(a: Point, b: Point, c: Point)
  implicit def seq2Triangle(s: Seq[Point]) = Triangle(s(0), s(1), s(2))
  def area(t: Triangle): Double = {
    0.5*math.abs((t.b.x -t.a.x)*(t.c.y - t.a.y) -
                 (t.b.y -t.a.y)*(t.c.x - t.a.x))
  }
  def inside(p: Point, t: Triangle): Boolean = {
    val a1 = area(Triangle(p, t.b, t.c))
    val a2 = area(Triangle(t.a, p, t.c))
    val a3 = area(Triangle(t.a, t.b, p))
    math.abs(area(t) - a1 - a2 - a3) < 1e-4
  }
  def findTriangle(first: Seq[Point], second: Seq[Point]): Triangle = {
    first.combinations(3)
         .filter(t => second.forall(inside(_, t)))
         .minBy(area(_))
  }
  val first = List(Point(0, 0), Point(0, 10), Point(10, 0),
                   Point(0, 5), Point(5, 0), Point(3, 3))
  val second = List(Point(1, 2), Point(2, 3), Point(1, 3))
  println(findTriangle(first, second))
}

Результат:

Triangle(Point(0.0,0.0),Point(0.0,5.0),P oint(3.0,3.0))

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

@iiyuijkhgfjf · 22.07.2013, 15:30 **[ТС]**

kamre, конечно, спасибо за помощь, но я бы еще хотел бы еще со своим вариантом решения разобраться.

Собственно что я имею и что уже сделал:

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
public class Point 
{
    double x; //koordinati tochek
    double y; //koordinati tochek
    public Point(double x, double y)
    {
        this.x = x;
        this.setY(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 + "||" + getY() + ")";
    }
    double getY() {
        return 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
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
public class Triangle 
{
    Point pointA;
    Point pointB; 
    Point pointC;
    public Triangle(Point pointA, Point pointB, Point pointC)
    {
        this.pointA = pointA;
        this.pointB = pointB;
        this.pointC = pointC;    
    }
    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(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(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)
        {
            // точек не найдено.
        }
        else
        {
            // точки найдены, площадь.
        }
    }
}

вот.

Где у меня возникли трудности:
Строчки 75 и 79 (метод minTriangle)

Java
1
Triangle triangle(arrayA[i], arrayA[j], arrayA[k]);

И

Java
1
if(triangle.inTriangle(arrayB[m]) && (areaMin = 0 || (triangle.area() <= areaMin))

Вот на эти две строчки мне компьютер ругается (вернее эклипс)
Честно говоря, я понятия не имею из-за чего он мне ругается. Может кто подскажет в чем проблема?

Я в самом конце кода поставил комментарии:
// точек не найдено.
// точки найдены, площадь.
Что мне писать на месте второго комментария (нужно, чтобы выводил площадь минимального треугольника и его координаты вершин) - задумка на этот счет есть, НО мне нужно знать еще и ваше мнение на этот счет.
За помощь буду благодарен.

@kamre · 22.07.2013, 15:38

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

Java
1
Triangle triangle(arrayA[i], arrayA[j], arrayA[k]);

Это же не C++ какой-нибудь, в Java надо так:

Java
1
Triangle triangle = new Triangle(arrayA[i], arrayA[j], arrayA[k]);

@iiyuijkhgfjf · 22.07.2013, 15:43 **[ТС]**

Ах да, точно, а я то думаю...
Но, почему-то все равно ругается

Java
1
Triangle triangle = new Triangle(arrayA[i], arrayA[j], arrayA[k]);

теперь на

Java
1
triangle

@Sakralbar · 22.07.2013, 16:02

iiyuijkhgfjf, Вы заново обьявляете переменную triangle, которая была передана как параметр функции.

@iiyuijkhgfjf · 22.07.2013, 16:26 **[ТС]**

т.е мне нужно сделать что-то наподобе этого:

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 Triangle minTriangle(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 triangle1 = new Triangle(arrayA[i], arrayA[j], arrayA[k]);
                    {
                        for(int m = 0; m<arrayB.length; m++)
                        {
                            if(triangle1.inTriangle(arrayB[m]) && (areaMin = 0 || (triangle1.area() <= areaMin))
                            {
                                areaMin = triangle1.area();
                                A = i;
                                B = j;
                                C = k;
                            }
                        }
                    }
                }
            }
        }

Добавлено через 29 секунд
triangle поменял на triangle1

@Sakralbar · 22.07.2013, 16:36

iiyuijkhgfjf, именно.

@iiyuijkhgfjf · 22.07.2013, 16:39 **[ТС]**

Спасибо, а можете что-нибудь сказать на счет строчки 19

Java
1
 if(triangle1.inTriangle(arrayB[m]) && (areaMin = 0 || (triangle1.area() <= areaMin))

Ругается. А почему - понять не могу.

@Sakralbar · 22.07.2013, 16:42

iiyuijkhgfjf, присваиваете

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

areaMin = 0

вместо сравнения areaMin == 0.

Не по теме:

Вообще Eclipse почти всегда дает достаточно информации для локализации ошибки. Не упрек, но совет =)

@iiyuijkhgfjf · 22.07.2013, 16:46 **[ТС]**

Sakralbar, спасибо.
Можете, пожалуйста, сказать свои мысли по по поводу:

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

Я в самом конце кода поставил комментарии:
// точек не найдено.
// точки найдены, площадь.
Что мне писать на месте второго комментария (нужно, чтобы выводил площадь минимального треугольника и его координаты вершин) - задумка на этот счет есть, НО мне нужно знать еще и ваше мнение на этот счет.
За помощь буду благодарен.

@Sakralbar · 23.07.2013, 12:30

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

нужно, чтобы выводил площадь минимального треугольника и его координаты вершин

ну дык выводите

@iiyuijkhgfjf · 23.07.2013, 16:41 **[ТС]**

Здравствуйте.
При реализации задачи столкнулся с некоторой загвосткой.
В методе minTriangle я возвращаю null, если треугольник не найден и возвращаю треугольник (объект) если он найден.
Вопрос следующий:
Я возвращаю треугольник:

Java
1
return triangle;

Но на эту строчку мне компьютер чего-то ругается понять не могу почему.
Вот, сам код:

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
public class Triangle 
{
    Point pointA;
    Point pointB; 
    Point pointC;
    public Triangle(Point pointA, Point pointB, Point pointC)
    {
        this.pointA = pointA;
        this.pointB = pointB;
        this.pointC = pointC;    
    }
    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)
    {
        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 triangle; 
            // точки найдены.
        }
    }
}

Повторюсь, мне нужно вернуть треугольник.

verylazy · 23.07.2013, 16:48

Java
1
2
public Triangle minTriangle(Point[] array)
Triangle triangle;

а там в коде исправить строку на

Java
1
triangle = new Triangle(arrayA[i], arrayA[j], arrayA[k]);

может пора поставить ide какую-то и не мучать себя и пистолет?

@Sakralbar · 23.07.2013, 16:52

iiyuijkhgfjf, переменная triangle видна только в цикле

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

for(int k = j+1; k<(arrayA.length); k++){ .... }

Чтобы она была видна во всем методе, нужно ее объявить в начале метода.

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

Не по теме:

verylazy, куда вперед батьки лезешь? Кыш! :D

@easybudda · 23.07.2013, 19:33

Как смог, набыдлокодил:

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
package easybudda.triangles;
 
import java.util.*;
 
public class MinAreaTriangle {
 
    public static void main(String[] args) {
        final int STARRY_POINTS_NUMBER = 5;
        final int TRIANGLE_POINTS_NUMBER = 100;
        
        Point [] starryPoints = new Point [ STARRY_POINTS_NUMBER ];
        Point [] trianglePoints = new Point [ TRIANGLE_POINTS_NUMBER ];
        Random rand = new Random();
        Set<Triangle> triangles = new TreeSet<>(new Comparator<Triangle>() {
            public int compare(Triangle a, Triangle b) {
                return ( a.getArea() - b.getArea() < 0.0 ) ? -1 : 1;
            }
        });
        
        for ( int i = 0; i < starryPoints.length; ++i )
            starryPoints[i] = new Point(rand.nextDouble() * 10.0, rand.nextDouble() * 10.0);
        for ( int i = 0; i < trianglePoints.length; ++i )
            trianglePoints[i] = new Point(rand.nextDouble() * 30.0, rand.nextDouble() * 30.0);
        
        for ( int i = 0; i < trianglePoints.length - 2; ++i ) {
            for ( int j = i + 1; j < trianglePoints.length - 1; ++j ) {
                for ( int k = j + 1; k < trianglePoints.length; ++k ) {
                    try {
                        Triangle t = new Triangle(trianglePoints[i], trianglePoints[j], trianglePoints[k]);
                        int p;
                        for ( p = 0; p < starryPoints.length; ++p )
                            if ( ! t.containPoint(starryPoints[p]) )
                                break;
                        if ( p == starryPoints.length )
                            triangles.add(t);
                    }
                    catch ( IllegalArgumentException e ) {
                        //...
                    }
                }
            }
        }
        
        if ( triangles.isEmpty() )
            System.out.println("Can't find any triangle contains all starry points.");
        else
            System.out.println("Min. area triangle: " + triangles.toArray()[0].toString());
        
        System.out.println("Starry points:");
        for ( Point pt : starryPoints )
            System.out.print(pt.toString() + " ");
        
        System.out.println("\nTriangle points:");
        for ( Point pt : trianglePoints )
            System.out.print(pt.toString() + " ");
        
        System.out.println("\nAll triangles:");
        for ( Triangle tr : triangles )
            System.out.println(tr.toString());
    }
 
}
 
class Point {
    private double x;
    private double y;
    
    Point(double _x, double _y) {
        x = _x;
        y = _y;
    }
    
    Point() {
        this(0.0, 0.0);
    }
    
    Point(Point p) {
        this(p.x, p.y);
    }
    
    boolean equalsTo(Point p) {
        return ( ( x == p.x ) && ( y == p.y ) );
    }
    
    void replaceTo(double _x, double _y) {
        x = _x;
        y = _y;
    }
    
    double getX() {
        return x;
    }
    
    double getY() {
        return y;
    }
    
    double distanceTo(Point p) {
        return Math.sqrt(Math.pow(p.x - x, 2.0) + Math.pow(p.y - y, 2.0));
    }
 
    public String toString() {
        return "(" + x + "; " + y + ")";
    }
}
 
class Triangle {
    private Point a;
    private Point b;
    private Point c;
    
    private double ab;
    private double bc;
    private double ac;
    private double area;
    
    Triangle(Point _a, Point _b, Point _c) throws IllegalArgumentException {
        ab = _a.distanceTo(_b);
        bc = _b.distanceTo(_c);
        ac = _c.distanceTo(_a);
        
        if ( ! ( ( ab < bc + ac ) && ( bc < ab + ac ) && ( ac < ab + bc ) ) )
            throw(new IllegalArgumentException());
        
        a = new Point(_a);
        b = new Point(_b);
        c = new Point(_c);
        
        area = calcArea();
    }
    
    private double calcArea() {
        double p = (ab + bc + ac) / 2.0;
        return Math.sqrt(p * (p - ab) * (p - bc) * (p - ac));
    }
    
    double getArea() {
        return area;
    }
    
    boolean containPoint(Point p) {
        double d1 = (a.getX() - p.getX()) * (b.getY() - a.getY()) - (b.getX() - a.getX()) * (a.getY() - p.getY());
        double d2 = (b.getX() - p.getX()) * (c.getY() - b.getY()) - (c.getX() - b.getX()) * (b.getY() - p.getY());
        double d3 = (c.getX() - p.getX()) * (a.getY() - c.getY()) - (a.getX() - c.getX()) * (c.getY() - p.getY());
        
        return ( ( d1 * d2 > 0 ) && ( d2 * d3 > 0 ) );
    }
    
    public String toString() {
        return "[A" + a.toString() + " B" + b.toString() + " C" + c.toString() + "]";
    }
}

сильно не смейтесь - первая програмка чуть крупнее "хелловорлд" на java, но за здоровую критику буду благодарен.

Алгоритм определения принадлежности точки треугольнику взял отсюда: https://www.cyberforum.ru/post800603.html
На бумажке проверял - вроде работает...

@mutagen · 24.07.2013, 00:36

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

Алгоритм определения принадлежности точки треугольнику

можно было заюзать стандартные формы Shape (конкретно Polygon), а потом на ней вызвать contains(x,y)

@iiyuijkhgfjf · 24.07.2013, 14:33 **[ТС]**

Здравствуйте.
Вот, подправил. Но все равно ругается на triangle.

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 = 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 triangle; 
            // точки найдены.
        }
    }
}

Товарищи, а вообще правильно я делаю, говоря return triangle? Может мне нужно возвращать areaMin?

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@Sakralbar 352 / 162 / 20 Регистрация: 22.12.2011 Сообщений: 352
	22.07.2013, 16:02
	iiyuijkhgfjf, Вы заново обьявляете переменную triangle, которая была передана как параметр функции. 0

@Sakralbar 352 / 162 / 20 Регистрация: 22.12.2011 Сообщений: 352
	22.07.2013, 16:36
	iiyuijkhgfjf, именно. 0