Добрый день! Помогите пожалуйста разобраться, где ошибка в задаче.
Задача:
Всем известно, что дачники – народ странный, почти такой же, как и программисты. Строят они свои дачи непонятно где, да и выращивают там непонятно что и непонятно зачем. А уж как они туда добираются, это другая история: кто на автобусе, кто на электричке, кто на автомобиле, ну а кто-то вовсе пешком ходит от дома и до самого участка. Так что не стоит удивляться, если вдруг Вы узнаете, что некое садоводческое товарищество располагается на острове, а дачники добираются до него самолетом. Да еще и на этом острове может не быть посадочной полосы, так что высадиться на остров можно, только прыгая с парашютом (мы уж не рассматриваем то, как они возвращаются с дач домой). Рассмотрим этот уникальный случай. Пилот всегда старается осуществить высадку парашютистов таким образом, чтобы дачники приземлялись как можно ближе к своим прямоугольным участкам. Пилоту интересно знать: сколько дачников приземлится на свои участки? Помогите ему решить эту задачу!
Входные данные:
В первой строке входного файла 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 получаются одинаковыми, хотя кроме второго дачника должны быть разными. В чем проблема подскажите пожалуйста.
Проблема в том, что вы считаете площадь, используя косое произведение, которое может быть отрицательным. Площадь же должна быть неотрицательной, то есть проще всего брать модуль. Другие улучшения: считать двойную площадь и тогда использовать целый тип (максимальное значение по условию: 2*(10^5)^2, вроде влезает), считать площадь прямоугольника как одно косое произведение.
Современные инструменты для криптотрейдинга: как технологии помогают принимать решения
Апостиль в Лос-Анджелесе без лишних нервов и бумажной волокиты
Основные этапы разработки сайта для стоматологической клиники
Продвижение своими сайтами как стратегия роста и независимости