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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 57, средняя оценка - 4.60
hepr
61 / 33 / 5
Регистрация: 21.10.2010
Сообщений: 539
#1

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

28.07.2011, 00:07. Просмотров 6950. Ответов 8
Метки нет (Все метки)

Здравствуйте, есть задание

Напишите функцию 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++
Нахождение площади параллелограмма, треугольника и объема параллелепипеда, тетраэдра по координатам вершин. Задается пользователем:...

Вычислить площадь правильного шестиугольника со стороной а, используя подпрограмму вычисления площади треугольника.через stdafx.h - C++
Вычислить площадь правильного шестиугольника со стороной а, используя подпрограмму вычисления площади треугольника.через stdafx.h..очень...

расчет площади треугольника - C++
Всем доброго времени суток! прошу помочь с заданием: Создать класс Triangle. Защищенные элементы класса - координаты трех точек:...

Задача о площади треугольника - C++
Следующий код не компилируется.Скажите пожалуйста почему #include&quot;stdafx.h&quot; #include&lt;iostream&gt; #include&lt;math.h&gt; double c; ...

Нахождение площади круга - C++
привет всем. кто может написать код для этой задачи: Дан круг с радиусом R, задать R и вычислить площадь круга(где R является...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт С++
1904 / 1436 / 109
Регистрация: 29.05.2011
Сообщений: 2,990
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
61 / 33 / 5
Регистрация: 21.10.2010
Сообщений: 539
28.07.2011, 00:32  [ТС]     Нахождение площади через координаты треугольника #3
Да, вы правы последнее из теоремы косинусов
Я вообще хотел сделать следующее, по координатам найти стороны(это вроде правильно)
По сторонам найти угол(через теорему косинусов), и далее найти площадь(1/2 * 1 сторону * 2 стороны * Sin(угла между ними))

Добавлено через 2 минуты
Думаю так будет правильнее (знак один изменил)
Блин, похоже не заметил, большое спасибо за помощь, проверил, вроде все работает!
grizlik78
Эксперт С++
1904 / 1436 / 109
Регистрация: 29.05.2011
Сообщений: 2,990
28.07.2011, 00:33     Нахождение площади через координаты треугольника #4
А вообще можно и без углов. Например с помощью формулы Герона
accept
4820 / 3240 / 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
380 / 272 / 21
Регистрация: 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
380 / 272 / 21
Регистрация: 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
380 / 272 / 21
Регистрация: 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++
//main.cpp int a,b,c; a=b=c=0; cin&gt;&gt;a&gt;&gt;b&gt;&gt;c; cout&lt;&lt;eqS(a,b,c); int eqS(int a,int b,int c){ int...

Функция вычисления площади треугольника - C++
Треугольник задан координатами своих вершин. (Используя процедуру выполнить расчёт длинны стороны треугольника. ) Вычислить площадь...


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

Или воспользуйтесь поиском по форуму:
accept
4820 / 3240 / 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     Нахождение площади через координаты треугольника
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru