Форум программистов, компьютерный форум CyberForum.ru

Нахождение площади через координаты треугольника - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 57, средняя оценка - 4.60
hepr
 Аватар для hepr
60 / 32 / 5
Регистрация: 21.10.2010
Сообщений: 538
28.07.2011, 00:07     Нахождение площади через координаты треугольника #1
Здравствуйте, есть задание

Напишите функцию square, вычисляющую площадь треугольника. С ее помощью для каждой из N точек определите, принадлежит ли точка заданному треугольнику.


Входные данные
Первая строка входного файла содержит координаты трех вершин треугольника x1, y1, x2, y2, x3, y3. Во второй строке записано натуральное число N. Далее в каждой из следующих N строк содержатся координаты точки, которую необходимо проверить на принадлежность треугольнику. Все числа во входном файле целые, по модулю не превосходящие 100.


Выходные данные
Для каждой из N точек на отдельной строке выведите слово YES, если точка принадлежит треугольнику или лежит на его границе, и слово NO - в противном случае.


Пример(ы)
input.txt
0 0 0 2 2 0
3
0 0
1 1
2 2

Пока остановимся чисто на нахождении площади
Я сделал программу
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "stdafx.h"
#include "iostream"
#include "math.h"
#include "vector"
#include "string"
 
#define PI 3.14159265
 
using namespace std;
struct point{
    int x;
    int y;
};
int _tmain(int argc, _TCHAR* argv[])
{
    vector<point> points;
    int x1,x2,x3,y1,y2,y3;
    FILE * file = fopen("input.txt","rt");
    fscanf(file, "%d", &x1);
    fscanf(file, "%d", &y1);
    fscanf(file, "%d", &x2);
    fscanf(file, "%d", &y2);
    fscanf(file, "%d", &x3);
    fscanf(file, "%d", &y3);
    int n;
    fscanf(file, "%d", &n);
    for(int a=0;a<n;a++)
    {
        point p;
        fscanf(file, "%d", &p.x);
        fscanf(file, "%d", &p.y);
        points.push_back(p);
    }
 
    cout << x1 << " " << y1 << endl;
    cout << x2 << " " << y2 << endl;
    cout << x3 << " " << y3 << endl;
 
    double wall1, wall2, wall3;
 
    wall1 = sqrt(pow(static_cast<double>(x1-x2),2.0)+pow(static_cast<double>(y1-y2),2.0));
    wall2 = sqrt(pow(static_cast<double>(x2-x3),2.0)+pow(static_cast<double>(y2-y3),2.0));
    wall3 = sqrt(pow(static_cast<double>(x1-x3),2.0)+pow(static_cast<double>(y1-y3),2.0));
 
    cout << "Walls: " <<  wall1 << " " << wall2 << " " << wall3 << endl;
    cout << "Pows: " << pow(wall1,2.0) << " " << pow(wall2,2.0) << " " << pow(wall3,2.0) << endl;
 
    double cos = (pow(wall2,2.0)-pow(wall1,2.0)-pow(wall3,2.0))/(2*wall2*wall3);
    cout << cos << endl;
    double ugol = acos(cos);
    cout << ugol << endl;
 
    double plosad = 0.5 * wall1 * wall2 * sin(ugol);
    cout << "pl= " << plosad << endl;
    system("pause");
    return 0;
}
Но ответ она выдает неправильный, не могли бы вы посмотреть в чем ошибка, я в принципе даже знаю где она - в вычислении косинуса, но почему она возникает не знаю
Заранее спасибо
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.07.2011, 00:07     Нахождение площади через координаты треугольника
Посмотрите здесь:

площадь треугольника, если известны координаты его углов. Введите координаты углов C++
расчет площади треугольника C++
C++ Даны координаты вершин треугольника и координаты некоторой точки внутри него
C++ Вычислить площадь правильного шестиугольника со стороной а, используя подпрограмму вычисления площади треугольника.через stdafx.h
C++ Задача о площади треугольника
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
28.07.2011, 00:29     Нахождение площади через координаты треугольника #2
Следующая строка
C++
1
wall1 = sqrt(pow(static_cast<double>(x1-x2),2.0)+pow(static_cast<double>(y1-y2),2.0));
может быть записана короче
C++
1
wall1 = hypot(x1 - x2, y1 - y2);
Не, ну можно и сюда ещё тоже касты добавить. А зачем?

Хоть бы пояснения дал какие, или ссылки на формулы (или сами формулы)
Это из теоремы косинусов что ли?
C++
1
double cos = (pow(wall2,2.0)-pow(wall1,2.0)-pow(wall3,2.0))/(2*wall2*wall3);
Название переменной плохое, так как есть общепринятая функция с таким названием.

Добавлено через 3 минуты
Думаю так будет правильнее (знак один изменил):
C++
1
    double cos = (pow(wall2,2.0)-pow(wall1,2.0)+pow(wall3,2.0))/(2*wall2*wall3);
hepr
 Аватар для hepr
60 / 32 / 5
Регистрация: 21.10.2010
Сообщений: 538
28.07.2011, 00:32  [ТС]     Нахождение площади через координаты треугольника #3
Да, вы правы последнее из теоремы косинусов
Я вообще хотел сделать следующее, по координатам найти стороны(это вроде правильно)
По сторонам найти угол(через теорему косинусов), и далее найти площадь(1/2 * 1 сторону * 2 стороны * Sin(угла между ними))

Добавлено через 2 минуты
Думаю так будет правильнее (знак один изменил)
Блин, похоже не заметил, большое спасибо за помощь, проверил, вроде все работает!
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
28.07.2011, 00:33     Нахождение площади через координаты треугольника #4
А вообще можно и без углов. Например с помощью формулы Герона
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
28.07.2011, 11:13     Нахождение площади через координаты треугольника #5
площадь треугольника:

S =
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{2} \left| \begin{vmatrix} x_1 & y_1 \\  x_2 & y_2 \end{vmatrix}  +  \begin{vmatrix} x_2 & y_2 \\  x_3 & y_3 \end{vmatrix}  +  \begin{vmatrix} x_3 & y_3 \\  x_1 & y_1 \end{vmatrix}  \right|
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
28.07.2011, 13:47     Нахождение площади через координаты треугольника #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
ВАРИАНТ 1

Точка D находится внутри треугольника ABC, если сума площадей тругольников ABD, BCD и ADC равна площади ABC.
Нахождение площади через координаты треугольника
В противном случае эта сума больше (см. рисунки)
Нахождение площади через координаты треугольника
Чтобы найти площадь воспользуемся псевдоскалярным произведением векторов. Произведение вычисляется как величина следующего определителя:
Название: det.png
Просмотров: 3801

Размер: 1.9 Кб
Раскроем его и получим выражение, на котором построена функция
C++
1
int area(pt a, pt b, pt c)
Нахождение площади через координаты треугольника
Далее в цикле проверяем это равенство для каждой точки.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <fstream>
#include <cmath>
 
struct pt
{
   int x;
   int y;
};
 
int area(pt a, pt b, pt c)
{
   return abs((a.x - c.x)*(b.y - c.y) + (b.x-c.x)*(c.y-a.y));
}
 
int main()
{
    pt a, b, c;
    std::ifstream fin("input.txt");
    fin >> a.x >> a.y
        >> b.x >> b.y
        >> c.x >> c.y;
 
    int n;
    fin >> n;
    for(int i = 0; i < n; i++)
    {
        pt d;
        fin >> d.x >> d.y;
        if(area(a, b, c) == area(a, b, d) + area(a, d, c) + area(b, d, c))
            std::cout << "YES" << std::endl;
        else
            std::cout << "NO"  << std::endl;    
    }
 
    return 0;
}
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
28.07.2011, 14:26     Нахождение площади через координаты треугольника #7
ВАРИАНТ 2
Воспользуемся тем свойством, что псевдоскалярное произведение из первого варианта меньше нуля, если тройка точек направлена по часовой стрелке. Проверим это для каждой из сторон, точек противоположных им, а также проверяемой точки. Если точка лежит внутри, то порядок обхода должен совпадать с точкой, противоположной даной стороне. Вышло несколько запутано, вот пример:
Нахождение площади через координаты треугольника
Берем сторону АВ. Точки А, В, С и A, B, D направлены за часовой стрелкой. Такое условие выполняется для каждой из сторон. Значит, точка лежит внутри треугольника.
Теперь точка D лежит снаружи:
Нахождение площади через координаты треугольника
и для стороны ВС даное условие не выполняется:
BСD - против часовой стрелкой, BCА - за часовой.
Такую проверку делает следующий код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <fstream>
 
struct pt
{
    int x;
    int y;
};
 
bool status(pt X, pt Y, pt is1, pt is2)
{
   int first  = (is1.x - X.x)*(Y.y - X.y) - (Y.x - X.x)*(is1.y - X.y);
   int second = (is2.x - X.x)*(Y.y - X.y) - (Y.x - X.x)*(is2.y - X.y);
   if (first > 0 && second < 0) return 0;
   if (second > 0 && first < 0) return 0;
   return 1;
}
 
int main(int argc, char **argv)
{
    pt a, b, c;
    std::ifstream fin("input.txt");
    fin >> a.x >> a.y
        >> b.x >> b.y
        >> c.x >> c.y;
    int n;
    fin >> n;
    for(int i = 0; i < n; i++)
    {
        pt d;
        fin >> d.x >> d.y;
        if(
            status(a, b, c, d) && status(b, c, a, d) &&
            status(a, c, b, d)
          )
            std::cout << "YES" << std::endl;
        else
            std::cout << "NO"  << std::endl;    
    }
 
   return 0;
}
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
28.07.2011, 15:00     Нахождение площади через координаты треугольника #8
Вот реализация формулы Герона, котрую можно применить для вычисления площади в первом варианте. Но так будет намного дольше.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <fstream>
#include <cmath>
 
struct pt
{
    int x;
    int y;  
};
 
float length(pt a, pt b)
{
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); 
}
 
 
int main(int argc, char **argv)
{
    std::ifstream fin("input.txt");
    pt a, b, c;
    fin >> a.x >> a.y
        >> b.x >> b.y
        >> c.x >> c.y;
    
    float aLength = length(b, c);
    float bLength = length(a, c);
    float cLength = length(a, b);
    
    float p = (aLength + bLength + cLength) / 2;
    
    float S = sqrt(p*(p-aLength)*(p-bLength)*(p-cLength));
    
    std::cout << "ÏëîùГ*äü òðåóãîëüГ*ГЁГЄГ*: " << S << std::endl;
 
    return 0;   
}
Добавлено через 15 минут
ДРУГИЕ ВАРИАНТЫ

-----------------------------------------------------------------------------------------------------------
Уравнение прямой вида Ах + By + С = 0 обладает следующим свойством. Если
в него подставить координаты точки, принадлежащей этой прямой, то оно превратится в тождество. Если точку взять из одной из полуплоскостей, на которые прямая делит плоскость, то будет выполняться неравенство Ах + By + С < 0, а если из другой - то Ах + By + С > 0. Выполняем такую проверку для каждой из сторон, противоположной и проверяемой точки. Решение аналогично варианту 2, но требует сопоставления уравнения прямой, проходящей через две точки.
-----------------------------------------------------------------------------------------------------------
Если точка находится строго внутри треугольника, то сумма углов, под которыми
из нее видны стороны, равна 2pi(pi=3.14). Если точка находится вне треугольника, то эта
сумма меньше 2pi.
Долго и трудности с углами.
-----------------------------------------------------------------------------------------------------------
Z-координата (аппликата) векторного произведения векторов, находящихся на
плоскости xOy, равная (х2-x1)(y3-y1) - (x3-x1)(y2-y1) обладает следующим
свойством: если угол поворота от первого вектора до второго составляет от 0 до 180°
по часовой стрелке, она имеет один знак, а если, наоборот, от 0 до 180° против часо-
вой стрелки, ее знак противоположен. Когда векторы коллинеарны, Z-координата
равна 0.
Таким образом, нужно найти три числа: Z-координаты векторных произведений
[DA, DB], [DB, DC], [DC, DA]. Если среди них есть и положительное, и отрицательное, точка лежит вне треугольника, в противном случае - внутри.
Ещё сложнее и
-----------------------------------------------------------------------------------------------------------

И почему в расширенном режиме нет редактора формул????

Добавлено через 4 минуты
К сожалению, нет времени для реализации каждого варианта...

Почитать по этой теме:
site1

Меньшиков Ф. - Олимпиадные задачи по программированию
Порублёв. Алгоритмы и программы. Решение олимпиадных задач
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2011, 03:08     Нахождение площади через координаты треугольника
Еще ссылки по теме:

Вычисление площади треугольника по координатам x,y C++
Нахождение площади параллелограмма, треугольника и объема параллелепипеда, тетраэдра по координатам вершин C++
Заданы координаты вершин треугольника. Вывести их в порядке обхода треугольника по часовой стрелке C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
29.07.2011, 03:08     Нахождение площади через координаты треугольника #9
Цитата Сообщение от Mayonez
Чтобы найти площадь воспользуемся псевдоскалярным произведением векторов.
C++
1
2
3
4
int area(pt a, pt b, pt c)
{
   return abs((a.x - c.x)*(b.y - c.y) + (b.x-c.x)*(c.y-a.y));
}
это площадь параллелограмма
Python
1
2
3
4
5
6
>>> def area(a, b, c):
...     return abs((a[0] - c[0]) * (b[1] - c[1]) + (b[0] - c[0]) * (c[1] - a[1]));
... 
>>> area((0, 0), (2, 0), (0, 2))
4
>>>
Yandex
Объявления
29.07.2011, 03:08     Нахождение площади через координаты треугольника
Ответ Создать тему
Опции темы

Текущее время: 09:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru