Кухня(); Задание N53

Правила [Одномерные массивы] 53. В одномерном массиве с четным количеством элементов (2N) находятся координаты N точек плоскости. Они располагаются в следующем порядке: x1, y1, х2, y2, x3, y3, и т.д. (xi, yi – целые). Определить номера точек, которые могут являться вершинами квадрата. Кухня(); Задание N53 - 2

Комментарии (12)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

Airon Уровень 34

22 сентября 2014

Хотелось как лучше, а получилось как всегда — гора условий… Самое сложное это как всегда адекватно проверить, но вроде работает и с учетом поворота оси квадрата. Вообщем надо было сначала залезть в геометрию, а не рисовать картину из треугольников. Итак Бермудский треугольник:

public static int getLengthSquared(int x1, int y1, int x2, int y2) {
    return ((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2));
}

public static boolean isAllIncluded(int[] p, int[] n) {    // если такое решение уже имело место быть, планировалось передавать сюда по 8 элементов
    label1:
    for (int i = 0; i < n.length; i += 2) {
        for (int j = 0; j < p.length; j += 2)
            if ((n[i] == p[j] && n[i + 1] == p[j + 1]))
                continue label1;
        return false;
    }
    return true;
}

public static boolean isWas(int[] p, int[] n) {    // формирование тех 8ми элементов, 4 вершины квадрата
    for (int i = 0; i < p.length; i += 8)
        if (isAllIncluded(Arrays.copyOfRange(p, i, i + 8), n))
            return false;
    return true;
}

public static int[] getIndexPointSquare(int... p) {
    if (p.length < 8 || p.length % 2 != 0)
        throw new IllegalArgumentException("Bad array");
    int[] temp = new int[0];
    for (int i = 0; i < p.length - 6; i += 2)
        for (int k = i + 2; k < p.length - 4; k += 2)
            for (int m = k + 2; m < p.length - 2; m += 2) {
                int a = getLengthSquared(p[i], p[i + 1], p[k], p[k + 1]);
                int b = getLengthSquared(p[i], p[i + 1], p[m], p[m + 1]);
                int c = getLengthSquared(p[k], p[k + 1], p[m], p[m + 1]);
                if ((((a == b + c) && b == c) ^ ((c == a + b) && a == b)) ^ ((b == a + c) && a == c))  // проверка чтобы выполнялось только 1 из 3 условий - треугольник с прямым углом + так как это квадрат оба катета равны
                    for (int j = i + 6; j < p.length; j



  aiv
      Уровень 27

      

      
    18 сентября 2014
      
  Кроме тупого перебора всех четверок точек других решений пока на ум не приходит:


    public static void squares(double... points)
    {
        if (points == null || points.length % 2 == 1 || points.length < 8)
            throw new IllegalArgumentException("Illegal points...");

        double[] temp = new double[8];
        for (int i = 0; i < points.length - 6; i += 2)
        {
            temp[0] = points[i];
            temp[1] = points[i + 1];
            for (int j = i + 2; j < points.length - 4; j += 2)
            {
                temp[2] = points[j];
                temp[3] = points[j + 1];
                for (int k = j + 2; k < points.length - 2; k += 2)
                {
                    temp[4] = points[k];
                    temp[5] = points[k + 1];
                    for (int l = k + 2; l < points.length; l += 2)
                    {
                        temp[6] = points[l];
                        temp[7] = points[l + 1];

                        if (isSquare(temp))
                        {
                            for (double coord : temp)
                                System.out.print(coord + " ");
                            System.out.println();
                        }
                    }
                }
            }
        }
    }

    public static boolean isSquare(double[] rectangle)
    {
        double[] temp = rectangle.clone(); // чтобы не изменить исходный массив при сортировке.
     
        sortPoints(temp);

        double side1 = dist(temp[0], temp[1], temp[2], temp[3]);
        double side2 = dist(temp[0], temp[1], temp[4], temp[5]);
        double side3 = dist(temp[2], temp[3], temp[6], temp[7]);
        double side4 = dist(temp[4], temp[5], temp[6], temp[7]);
        double diag1 = dist(temp[0], temp[1], temp[6], temp[7]);
        double diag2 = dist(temp[2], temp[3], temp[4], temp[5]);


  

  aiv
      Уровень 27

      

      
    18 сентября 2014
      
  С таким методом, по-моему тоже должно работать:


    public static boolean isSquare(double[] rectangle)
    {
        double[] temp = rectangle.clone(); // чтобы не изменить исходный массив при сортировке.

        sortPoints(temp);

        double side1 = dist(temp[0], temp[1], temp[2], temp[3]);
        double side2 = dist(temp[0], temp[1], temp[4], temp[5]);
        double diag1 = dist(temp[0], temp[1], temp[6], temp[7]);
        double diag2 = dist(temp[2], temp[3], temp[4], temp[5]);
        return ((side1 == side2) && (diag1 == diag2));
    }


  


  aiv
      Уровень 27

      

      
    18 сентября 2014
      
  Хотя нет, не прокатит, уже сам нашел почему :-(

  


  aiv
      Уровень 27

      

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


    public static boolean isSquare(double[] rectangle)
    {
        double eps = 1E-9; // точность вычислений.
        double[] temp = rectangle.clone(); // чтобы не изменить исходный массив при сортировке.

        sortPoints(temp);

        double side1 = dist(temp[0], temp[1], temp[2], temp[3]);
        double side2 = dist(temp[0], temp[1], temp[4], temp[5]);
        double side3 = dist(temp[2], temp[3], temp[6], temp[7]);
        double side4 = dist(temp[4], temp[5], temp[6], temp[7]);
        double diag1 = dist(temp[0], temp[1], temp[6], temp[7]);
        double diag2 = dist(temp[2], temp[3], temp[4], temp[5]);
        return ((side1 - side2 < eps) &&
                (side2 - side3 < eps) &&
                (side3 - side4 < eps) &&
                (diag1 - diag2 < eps));
    }


  


  aiv
      Уровень 27

      

      
    18 сентября 2014
      
  Еще проще придумал проверку на квадрат — по расстояниям между координатами:


    public static boolean isSquare(double[] rectangle)
    {
        double[] temp = rectangle.clone(); // чтобы не изменить исходный массив при сортировке.

        sortPoints(temp);

        double x2x1 = temp[2] - temp[0];
        double x4x3 = temp[6] - temp[4];
        double y2y1 = temp[3] - temp[1];
        double y4y3 = temp[7] - temp[5];
        double x4x1 = temp[6] - temp[0];
        double y3y2 = temp[5] - temp[3];
        double x3x2 = temp[4] - temp[2];
        double y4y1 = temp[7] - temp[1];

        return ((x2x1 == x4x3) &&
                (y2y1 == y4y3) &&
                (       ((x4x1 == y3y2) && (x3x2 == -y4y1)) ||
                        ((x4x1 == -y3y2) && (x3x2 == y4y1))
                )
        );
    }



  Docktor91
      Уровень 40

      

      
    18 сентября 2014
      
  так то все они могут являться вершинами квадрата)))

если самого маленького квадрата, куда входят все точки, то…

public static int getPointIndexWithMaxDistanceFromCenter(int... p)
{
    if (p == null || p.length % 2 == 1 || p.length == 0)
        throw new IllegalArgumentException("No-no-no");
    int res = 0;          //is index
    for (int i = 0; i < p.length; i += 2)
        res = (p[res] * p[res] + p[res + 1] * p[res + 1]) < (p[i] * p[i] + p[i + 1] * p[i + 1]) ? i : res;
    return res;
}
public static void printVertexOfSquare(int... p)
{
    int ind=getPointIndexWithMaxDistanceFromCenter(p);
    for (int i = 0 ; i < p.length; i += 2)
    {
    	
        if ( (p[i] == p[ind] || p[i] == -p[ind] ) && (p[i + 1] == p[ind + 1] || p[i + 1] == -p[ind + 1]))
            System.out.println(String.format("(%d, %d)",p[i],p[i+1]));
    }
}


  

  LastLost
      Уровень 41

      

      
    18 сентября 2014
      
  или все квадраты, сформированные из точек, входящих в массив

  


  Docktor91
      Уровень 40

      

      
    18 сентября 2014
      
  ну да точно, найти сумму всех квадратов, и все элементы с макс суммой будут искомые вершины

  


  LastLost
      Уровень 41

      

      
    18 сентября 2014
      
  скорее искать точки (Xi, Yk), (Xi,Ym), (Xj, Yk), (Xj, Ym), где (Xi — Xj) == (Ym -Yk)

  


  aiv
      Уровень 27

      

      
    18 сентября 2014
      
  Точки (0,2) (1,0) (2,3) (3,1) тоже квадрат, только наклонившийся, соответственно Xi, Xj, Ym, Yk в Ваших формулах будут разные.

  


  LastLost
      Уровень 41

      

      
    18 сентября 2014
      
  что усугубляет это всё :)