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

Определить принадлежит ли точка треугольнику - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 40, средняя оценка - 4.68
MilitaNt
0 / 0 / 0
Регистрация: 15.06.2012
Сообщений: 21
16.06.2012, 11:29     Определить принадлежит ли точка треугольнику #1
Здравствуйте! Не могли бы вы помочь решить мне задачу?
Всем буду очень благодарен

В декартовой системе координат на плоскости заданы координаты вершин треугольника и еще одной точки. Определить, принадлежит ли эта точка треугольнику.
Ввод из файла INPUT.TXT. В четырех строках находятся пары чисел - координаты точек. Числа в первых трех строках - это координаты вершин треугольника, в четвертой строке - координаты тестируемой точки.
Вывод в файл OUTPUT.TXT. Вывести In, если точка находится внутри треугольника, или Out - если снаружи.
Ограничения: координаты вершин - целые числа, для любой точки выполняются следующие условия: -10^9 ≤ x, y ≤ 10^9, время 1 с.
Примеры
Ввод 1 Ввод 2 Ввод 3 Ввод 4
0 0 0 0 0 0 0 0
100 0 100 0 100 0 100 0
0 100 0 100 0 100 0 100
100 100 10 10 50 50 0 0
Вывод 1 Вывод 2 Вывод 3 Вывод 4
Out In In In

Добавлено через 1 час 1 минуту
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.06.2012, 11:29     Определить принадлежит ли точка треугольнику
Посмотрите здесь:

C++ Треугольник задан вершинами (x1,y1), (x2,y2), (x3,y3). Принадлежит ли заданная точка (x,y) указанному треугольнику.
C++ принадлежит ли точка с координатами (x, y) треугольнику
C++ Дана точка A(x; y) на координатной плоскости. Определить, принадлежит ли она треугольнику с вершинами в точках .
C++ Даны отрезки [a, b] и [c, d] и точка A с координатой х. Определить, принадлежит ли данная точка одному из этих отрезков, обоим или лежит вне их
Определить, принадлежит ли данная точка треугольнику C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
16.06.2012, 13:02     Определить принадлежит ли точка треугольнику #2
Допустим, мы уже сделали ввод данных. Тогда рассмотрим расположение вершин и точки по оси х. Возможны такие варианты: 1) абсцисса точки не лежит между абсцисс вершин -- точка очевидно снаружи
2) абсцисса точки лежит между абсциссами вершин (обозначим их как вершина 1 и вершина 2). Тогда (нарисуйте рисуночек) линия, проведенная паралельно оси ординат через точку пересечет 2 стороны треугольника. Нам лишь надо проверить, где находится точка относительно пересечений -- между ними или нет. Если между, то она внутри, иначе -- снаружи
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
16.06.2012, 13:18     Определить принадлежит ли точка треугольнику #3
UFO94, а зачем так сложно?
надо просто вычислить площадь заданного треугольнка, и еще трех треугольников которые получаются с помощью четветой точки, и если площадь заданного равна площади тех трех то точка в треугольнике.
кстати это решение проверено
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
16.06.2012, 20:15     Определить принадлежит ли точка треугольнику #4
Черт... А слона-то я и не приметил...
aram_gyumri, спасибо!

Добавлено через 9 минут
Ну, зато мой метод будет работать на невыпуклых многоугольниках)
darkknight2008
 Аватар для darkknight2008
61 / 61 / 6
Регистрация: 16.10.2011
Сообщений: 200
16.06.2012, 20:41     Определить принадлежит ли точка треугольнику #5
Вообще точка лежит внутри треугольника, если она находится по одну сторону от всех прямых, содержащих его стороны. Считать площади 3х треугольников обременительно...
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
16.06.2012, 22:24     Определить принадлежит ли точка треугольнику #6
ИМХО, считать площади и проверять, по какую сторону от прямой точка -- по ту же, где третья вершина, или по другую -- обе задачи несложные.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
16.06.2012, 22:44     Определить принадлежит ли точка треугольнику #7
Несложные-то они несложные, только вторую точно можно решать в целых числах и избежать таким образом ошибок, связанных с округлениями, а вот в случае площадей я не уверен.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
17.06.2012, 00:49     Определить принадлежит ли точка треугольнику #8
grizlik78, это 100% верное решение проверено на ********
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.04.2015, 11:38     Определить принадлежит ли точка треугольнику
Еще ссылки по теме:

C++ Определить, принадлежит ли точка M(x,y)
C++ Определить принадлежит ли точка треугольнику
C++ Определить, принадлежит ли точка графику

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

Или воспользуйтесь поиском по форуму:
CrazzyBeer
 Аватар для CrazzyBeer
3 / 3 / 2
Регистрация: 24.03.2014
Сообщений: 65
15.04.2015, 11:38     Определить принадлежит ли точка треугольнику #9
Решение основано на площадях, которые вычисляются через векторное произведение.
Прошло все тесты на одном из сайтов с задачами.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <stdlib.h>
int area(int ax,int ay,int bx,int by,int cx,int cy) {
    return abs((by-ay)*(cx-ax)-(bx-ax)*(cy-ay));
}
 
int main() {
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int ax,ay,bx,by,cx,cy,px,py;
    scanf("%d%d%d%d%d%d%d%d",&ax,&ay,&bx,&by,&cx,&cy,&px,&py);
    int s=area(ax,ay,bx,by,cx,cy),s1=area(ax,ay,bx,by,px,py),s2=area(bx,by,cx,cy,px,py),s3=area(cx,cy,ax,ay,px,py);
    if (s1+s2+s3-s<=0) printf("In"); else printf("Out");
 
}
Yandex
Объявления
15.04.2015, 11:38     Определить принадлежит ли точка треугольнику
Ответ Создать тему
Опции темы

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