• ,

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


Правила
[Одномерные массивы]
70. В одномерном массиве с четным количеством элементов (2N) находятся координаты N точек плоскости. Они располагаются в следующем порядке: x1, y1, х2, y2, x3, y3, и т.д. Определить три точки, которые являются вершинами треугольника, для которого разность числа точек вне его и внутри является минимальной.

Перед тем как постить код,
Порасспрашивал народ.
Как красиво написать,
Что бы в кайф было читать?!

Ctrl Alt L — Reformat Code
Run и пост готов, вперед!
Что еще вам нужно знать,
Не забудьте рассказать!:)

3 комментария

Vash_the_Stampede
public static void solve(double[] arr) {
    int n = arr.length / 2;
    int i1 = 0, i2 = 0, i3 = 0;
    int min = n;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                int count = 0;

                for (int l = 0; l < n; l++) {
                    if (i == l || j == l || k == l)
                        continue;

                    count += isInside(arr[2 * l], arr[2 * l + 1],
                            arr[2 * i], arr[2 * i + 1],
                            arr[2 * j], arr[2 * j + 1],
                            arr[2 * k], arr[2 * k + 1]);
                }

                count = Math.abs(count);

                if (count < min) {
                    min = count;
                    i1 = i;
                    i2 = j;
                    i3 = k;
                }
            }
        }
    }

    System.out.printf("i1 = %d, i2 = %d, i3 = %d\n", i1, i2, i3);
}

public static double area(double x1, double y1, double x2, double y2, double x3, double y3) {
    double a = Math.hypot(x1 - x2, y1 - y2);
    double b = Math.hypot(x2 - x3, y2 - y3);
    double c = Math.hypot(x3 - x1, y3 - y1);

    double p = (a + b + c) / 2;

    return Math.sqrt(p * (p - a) * (p - b) * (p - c));
}

public static int isInside(double x, double y, double x1, double y1, double x2, double y2, double x3, double y3) {
    double s = area(x1, y1, x2, y2, x3, y3);

    double s1 = area(x, y, x1, y1, x2, y2);
    double s2 = area(x, y, x2, y2, x3, y3);
    double s3 = area(x, y, x3, y3, x1, y1);

    if (s1 == 0 || s2 == 0 || s3 == 0)
        return 0;

    return s == s1 + s2 + s3 ? 1 : -1;
}
Vash_the_Stampede
  • Vash_the_Stampede
  • 0
  • Комментарий отредактирован 2014-10-15 15:29:08 пользователем Vash_the_Stampede
так скажем, вроде решение «в лоб». функция area() возвращает площадь треугольника по координатам трех точек. функция isİnside возвращает 1, 0 или -1 если точка(x, y) находится внутри треугольника, на его стороне и снаружи соответственно. в главной функции пробегаем по всем тройкам точек, для каждой считаем пробегаем по всем остальным точкам и подсчитываем разность… дальше, надеюсь, понятно
Vash_the_Stampede
Десять негритят отправились обедать,
Один поперхнулся, их осталось девять.
Девять негритят, поев, клевали носом,
Один не смог проснуться, их осталось восемь.
Восемь негритят в Девон ушли потом,
Один не возвратился, остались всемером.
Семь негритят дрова рубили вместе,
Зарубил один себя и осталось шесть их.
Шесть негритят пошли на пасеку гулять,
Одного ужалил шмель, их осталось пять.
Пять негритят судейство учинили,
Засудили одного, осталось их четыре.
Четыре негритенка пошли купаться в море,
Один попался на приманку, их осталось трое.
Трое негритят в зверинце оказались,
Одного схватил медведь, и вдвоем остались.
Двое негритят легли на солнцепеке,
Один сгорел и вот один, несчастный, одинокий
Последний негритенок поглядел устало,
Он пошел повесился, и никого не стало!
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.