0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
1

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

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

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

Небольшое лирическое отступление. Тут я такую задачу встречал много раз и все, за исключением одной (написанная на паскале) были проигнорированны и попросту забыты - утонули в дебрях других тем. Кто знает, не отвечали потому, что не отвечали, либо не было желания объяснять что и как, либо, что вероятнее всего, не написали из-за того, что человек, который просил решения, просто "скопипастит" задачу и все... и уход в затемнение, короче - просто сдаст и забудет... НО это всего лишь догадки, не более того. А чего я хочу? Бляха, просто понять эту задачу, нет, смысл я ее понял и как реализовывать примерно знаю, НО есть некотарая проблема - не все места я знаю как написать.
Ну да ладно.
Вот код:
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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.07.2013, 22:11
Ответы с готовыми решениями:

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

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

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

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

29
ɐwʎ ɔ vǝmоɔ dиw ɐʚонɔ
443 / 442 / 100
Регистрация: 14.10.2012
Сообщений: 1,146
Записей в блоге: 9
17.07.2013, 23:41 2
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;
        .....
1
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
18.07.2013, 20:17  [ТС] 3
Здравствуйте.
Да, именно второй вариант, а именно "мы помогли именно с методами определения плоскостей и координат" вот в этом загвостка.

Добавлено через 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;
        }
    }
}
0
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
21.07.2013, 22:27 4
До чего же много в 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),Point(3.0,3.0))
Массив: Выбрать три различные точки первого множества так, чтобы треугольник с вершинами в этих точках накрывал все точки второго множества
1
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
22.07.2013, 15:30  [ТС] 5
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))
Вот на эти две строчки мне компьютер ругается (вернее эклипс)
Честно говоря, я понятия не имею из-за чего он мне ругается. Может кто подскажет в чем проблема?

Я в самом конце кода поставил комментарии:
// точек не найдено.
// точки найдены, площадь.
Что мне писать на месте второго комментария (нужно, чтобы выводил площадь минимального треугольника и его координаты вершин) - задумка на этот счет есть, НО мне нужно знать еще и ваше мнение на этот счет.
За помощь буду благодарен.
0
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
22.07.2013, 15:38 6
Цитата Сообщение от 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]);
0
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
22.07.2013, 15:43  [ТС] 7
Ах да, точно, а я то думаю...
Но, почему-то все равно ругается
Java
1
Triangle triangle = new Triangle(arrayA[i], arrayA[j], arrayA[k]);
теперь на
Java
1
triangle
0
352 / 162 / 20
Регистрация: 22.12.2011
Сообщений: 352
22.07.2013, 16:02 8
iiyuijkhgfjf, Вы заново обьявляете переменную triangle, которая была передана как параметр функции.
0
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
22.07.2013, 16:26  [ТС] 9
т.е мне нужно сделать что-то наподобе этого:
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
0
352 / 162 / 20
Регистрация: 22.12.2011
Сообщений: 352
22.07.2013, 16:36 10
iiyuijkhgfjf, именно.
0
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
22.07.2013, 16:39  [ТС] 11
Спасибо, а можете что-нибудь сказать на счет строчки 19
Java
1
 if(triangle1.inTriangle(arrayB[m]) && (areaMin = 0 || (triangle1.area() <= areaMin))
Ругается. А почему - понять не могу.
0
352 / 162 / 20
Регистрация: 22.12.2011
Сообщений: 352
22.07.2013, 16:42 12
iiyuijkhgfjf, присваиваете
Цитата Сообщение от iiyuijkhgfjf Посмотреть сообщение
areaMin = 0
вместо сравнения areaMin == 0.

Не по теме:

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

1
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
22.07.2013, 16:46  [ТС] 13
Sakralbar, спасибо.
Можете, пожалуйста, сказать свои мысли по по поводу:
Цитата Сообщение от iiyuijkhgfjf Посмотреть сообщение
Я в самом конце кода поставил комментарии:
// точек не найдено.
// точки найдены, площадь.
Что мне писать на месте второго комментария (нужно, чтобы выводил площадь минимального треугольника и его координаты вершин) - задумка на этот счет есть, НО мне нужно знать еще и ваше мнение на этот счет.
За помощь буду благодарен.
0
352 / 162 / 20
Регистрация: 22.12.2011
Сообщений: 352
23.07.2013, 12:30 14
Цитата Сообщение от iiyuijkhgfjf Посмотреть сообщение
нужно, чтобы выводил площадь минимального треугольника и его координаты вершин
ну дык выводите
0
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
23.07.2013, 16:41  [ТС] 15
Здравствуйте.
При реализации задачи столкнулся с некоторой загвосткой.
В методе 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; 
            // точки найдены.
        }
    }
}
Повторюсь, мне нужно вернуть треугольник.
0
Заблокирован
23.07.2013, 16:48 16
Java
1
2
public Triangle minTriangle(Point[] array)
Triangle triangle;
а там в коде исправить строку на
Java
1
triangle = new Triangle(arrayA[i], arrayA[j], arrayA[k]);
может пора поставить ide какую-то и не мучать себя и пистолет?
2
352 / 162 / 20
Регистрация: 22.12.2011
Сообщений: 352
23.07.2013, 16:52 17
iiyuijkhgfjf, переменная triangle видна только в цикле
Цитата Сообщение от iiyuijkhgfjf Посмотреть сообщение
for(int k = j+1; k<(arrayA.length); k++){ .... }
Чтобы она была видна во всем методе, нужно ее объявить в начале метода.

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

Не по теме:

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

1
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12458 / 7482 / 1753
Регистрация: 25.07.2009
Сообщений: 13,761
23.07.2013, 19:33 18
Как смог, набыдлокодил:
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
На бумажке проверял - вроде работает...
1
2586 / 2259 / 257
Регистрация: 14.09.2011
Сообщений: 5,185
Записей в блоге: 18
24.07.2013, 00:36 19
Цитата Сообщение от easybudda Посмотреть сообщение
Алгоритм определения принадлежности точки треугольнику
можно было заюзать стандартные формы Shape (конкретно Polygon), а потом на ней вызвать contains(x,y)
1
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 69
24.07.2013, 14:33  [ТС] 20
Здравствуйте.
Вот, подправил. Но все равно ругается на 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?
0
24.07.2013, 14:33
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.07.2013, 14:33
Помогаю со студенческими работами здесь

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

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru