-1

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

Задача:

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

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

В первой строке входного файла 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 получаются одинаковыми, хотя кроме второго дачника должны быть разными. В чем проблема подскажите пожалуйста.

1
  • ... получаются одинаковыми, хотя кроме второго дачника должны быть разными. Какое именно значение получается не таким как Вы ожидали? Если определить конкретный неправильный результат, то вопрос получится сократить до вида почему эта строка дает результат X, хотя должна Y. На такой вопрос Вам ответят быстрее. 6 июн 2017 в 13:08

1 ответ 1

3

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

6
  • Спасибо. А можно поподробнее, а то не совсем понятно. Где использовать модуль? Числа то все равно одинаковые.
    – miltan13
    6 июн 2017 в 14:40
  • @miltan13 Использовать модуль, когда вы вычисляете площадь. Например, так: areat += Math.abs(0.5* ((hum.coord[0][0] - hum.coord[i + 2][0]) ... ); 6 июн 2017 в 14:42
  • Поставил везде модуль. Результат: 1)12.0-12.0 2)24.0-18.0 3)8.0-8.0. Пишет что одинаковые первый и третий, хотя должен быть только второй(
    – miltan13
    7 июн 2017 в 8:40
  • @miltan13 Там не второй должен быть одинаковым, а число попавших на участок — 2. 7 июн 2017 в 8:44
  • Извиняюсь @pocketgulag , вы были правы. Это в задаче не правильные результаты были. Огромное спасибо!!!!))
    – miltan13
    7 июн 2017 в 8:49

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.