Задача на JAVA. Дачники

581
08 июня 2017, 06:17

Добрый день! Помогите пожалуйста разобраться, где ошибка в задаче.

Задача:

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

Входные данные:

В первой строке входного файла INPUT.TXT записано натуральное число N (1 ≤ N ≤ 1000) – количество дачников, далее идут N строк, в каждой из которых описаны координаты каждого дачника и его участка: X, Y, X1, Y1, X2, Y2, X3, Y3, X4, Y4 где X, Y – координаты приземления парашютиста X1, Y1, X2, Y2, X3, Y3, X4, Y4 – координаты прямоугольного участка на плоскости, указанные последовательно. Все координаты – целые числа, не превышающие 50000 по абсолютной величине

Выходные данные:

В выходной файл OUTPUT.TXT нужно вывести количество дачников, приземлившихся на свой участок. Попадание на границу участка считается попаданием на участок.

Пример

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

Вот программа:

import java.io.File;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
import static javafx.scene.input.KeyCode.N;
public class T_12  {
    static int N;
    PrintWriter pw;
    public static void main(String[] args) throws Exception {
        new T_12().run();
    }
    public void run() throws Exception {
        Scanner sc = new Scanner(new File("C:\\Users\\sbeskhmelnitskiy\\Desktop\\input.txt"));
        pw = new PrintWriter(new File("C:\\Users\\sbeskhmelnitskiy\\Desktop\\output.txt"));
        N = sc.nextInt();
        //Создаю дачников и считываю их координаты
        for (int i = 0; i < N; i++) {
            Human h = new Human();
            for (int t = 0; t < 5; t++) {
                for (int j = 0; j < 2; j++) {
                    h.coord[t][j] = sc.nextInt();
                }
            }
            //Передаю Дачника и его номер(для его вывода в файл если он попал к себе), на проверку.
            check_human (h, i);
        }
        pw.close();
    }
    public void check_human(Human hum, int num) throws Exception {
        double areat = 0, areas = 0;
        //Считаю площадь четырех треугольников(соеденил точку приземления с вершинами)
        for (int i = 0; i < 4; i++) {
            if (i < 3) {
                areat += 0.5 * ((hum.coord[0][0] - hum.coord[i + 2][0]) * (hum.coord[i + 1][1] - hum.coord[i + 2][1]) - (hum.coord[i + 1][0] - hum.coord[i + 2][0]) * (hum.coord[0][1] - hum.coord[i + 2][1]));
            } else {
                areat += 0.5 * ((hum.coord[0][0] - hum.coord[1][0]) * (hum.coord[i + 1][1] - hum.coord[1][1]) - (hum.coord[i + 1][0] - hum.coord[1][0]) * (hum.coord[0][1] - hum.coord[1][1]));
            }
        }
        //Считаю площать прямоугольника(разбил его на два треугольника и посчитал их площадь)
        areas = 0.5 * ((hum.coord[1][0] - hum.coord[3][0]) * (hum.coord[2][1] - hum.coord[3][1]) - (hum.coord[2][0] - hum.coord[3][0]) * (hum.coord[1][1] - hum.coord[3][1]));
        areas += 0.5 * ((hum.coord[3][0] - hum.coord[1][0]) * (hum.coord[4][1] - hum.coord[1][1]) - (hum.coord[4][0] - hum.coord[1][0]) * (hum.coord[3][1] - hum.coord[1][1]));
        if (areas == areat)
        pw.println (num+1);
    }
}
public class Human {
    double [][] coord = new double [5][2];
}

На выходе получается "1 2 3", а должна только "2". areas и areat получаются одинаковыми, хотя кроме второго дачника должны быть разными. В чем проблема подскажите пожалуйста.

Answer 1

Проблема в том, что вы считаете площадь, используя косое произведение, которое может быть отрицательным. Площадь же должна быть неотрицательной, то есть проще всего брать модуль. Другие улучшения: считать двойную площадь и тогда использовать целый тип (максимальное значение по условию: 2*(10^5)^2, вроде влезает), считать площадь прямоугольника как одно косое произведение.

READ ALSO
Заголовок OPTIONS при авторизации через JWT

Заголовок OPTIONS при авторизации через JWT

Делаю два сервисаОдин - фронт на Angular 2

314
Помогите разобраться с JList

Помогите разобраться с JList

Создал компонент Jlist и создаю таблицу для БД, заношу значение для БД в списокВсё работает, но проблема в том что когда я, к примеру, возвращаюсь...

281
Как реализовать подсветку обьекта в Swing?

Как реализовать подсветку обьекта в Swing?

Доброго времени сутокЕсть задание схематически отобразить человеческую фигуру руки ноги голова и тд

357