Опишите алгоритм, определяющий количество целочисленных точек, попавших внутрь треугольника

@katya · Регистрация: 21.03.2012

Студворк — интернет-сервис помощи студентам

помогите пожалуйста с решением! Даны координаты вершин треугольника на плоскости. Опишите алгоритм, определяющий количество целочисленных точек, попавших внутрь треугольника

@Cute · 15.06.2013, 00:22

Вот программа, составленная в среде Mathcad (см. рис.):

S(x1,y1,x2,y2,x3,y3) - функция, вычисляющая площадь треугольника по координатам его вершин $https://www.cyberforum.ru/cgi-bin/latex.cgi?({x}_{1},{y}_{1}), ({x}_{2},{y}_{2}), ({x}_{3},{y}_{3})$ ;

gcd(a,b) - наибольший общий делитель чисел a и b.

@katya · 16.06.2013, 13:25 **[ТС]**

уважаемые программисты, помогите эту задачу сделать на паскале...пожалуйста

@Klavdia · 17.06.2013, 10:16

Сообщение от katya

уважаемые программисты, помогите эту задачу сделать на паскале...пожалуйста

Может быть, сложить все точки под двумя отрезками прямых и вычесть оттуда все точки под третьим отрезком, т.е., примерно, так:

Int(X2) Int(X3) Int(X3)
∑ Int(A1*i+B1) + ∑ Int(A2*i+B2) - ∑ Int(A3*i+B3)
i=Int(X1+1) i=Int(X2+1) i=Int(X1+1)

где y=A1*x+B1, y=A2*X+B2, y=A3*x+B3 - уравнения прямых сторон тр-ка.
Не умею, пока, тут писать формулы, поясню, что первая сумма - от целого от Х1+1 до целого от Х2, вторая - от целого от Х2+1 до целого от Х3, третья - от целого от Х1+1 до целого от Х3.

@helter · 23.06.2013, 03:57

Сообщение от Cute

Вот программа, составленная в среде Mathcad (см. рис.):

Исключительно интересно! Это вы по формуле Пика?

@Cute · 23.06.2013, 07:46

Сообщение от helter

Исключительно интересно! Это вы по формуле Пика?

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

@katya · 24.06.2013, 23:39 **[ТС]**

@Cute, объясните пожалуйста, как задачу реализовать в паскале...

@Cute · 24.06.2013, 23:46

Сообщение от katya

@Cute, объясните пожалуйста, как задачу реализовать в паскале...

Извините, katya, в этом вопросе я не смогу вам помочь.

@katya · 24.06.2013, 23:46 **[ТС]**

очень жаль...

@helter · 24.06.2013, 23:51

Есть замечательная формула - формула Пика:
S = N - B/2 - 1/2
где S - площадь выпуклого многоугольника с целочисленными вершинами, N - число принадлежащих ему целочисленных точек, B - число целочисленных точек точек на границе.

Площадь треугольника находится по стандартной формуле аналитической геометрии.

Если a = (a1, a2) и b = (b1, b2) - целочисленные точки, то на отрезке [a, b] лежит НОД(b1 - a1, b2 - a2) + 1 целочисленных точек.

По-моему, это несложно реализовать на любом языке программирования. Правда, на паскале, наверно, придётся НОД отдельно писать. Но это пара строчек (алгоритм Евклида, рекурсия).

@katya · 24.06.2013, 23:55 **[ТС]**

если честно, то не понимаю как это реализовать в паскале..

@helter · 25.06.2013, 00:04

Я не забыл уже паскаль, как-то так:

Pascal
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
 { псевдокод!!! }
 
function s(x1, y1, x2, y2, x3, y3): integer;
begin
    s := ...
end;
 
function gcd(a, b): integer;
begin
    if a = 0 then
        gcd := b
    else
        a := abs(a);
        b := abs(b);
        if a < b then
            gcd := gcd(a, b mod a)
        else
            gcd := gcd(a mod b, b)
end;
 
function n(x1, y1, x2, y2, x3, y3): integer
    n := ... (формула Cute);
 
begin
    write('> ');
    readln(.....);
    writeln(....);
    readln
end.

@ermolay · 25.06.2013, 00:11

Количество целочисленных точек, попавших внутрь треугольника

@Denis123456789 · 25.06.2013, 01:05

Я думаю надо сначала задать в программе уравнения сторон треугольника. Затем сравниваем координаты точек с границами области. По y: берем координату х точки, вставляем ее в уравнения сторон треугольника, находим какие из уравнений сторон дают минимальные и максимальные y, это будут границы области снизу и сверху соответственно. Если y точки меньше (равен) верхней границы и больше (равен) нижней границе, то по y условие выполняется. По x: берем теперь y точки и вставляем в уравнения сторон треугольника, далее аналогично (только теперь получаем x), только теперь это левая и правая граница. Если оба условия выполнены, то точка входит в треугольник.
Но, наверное, криво написал

@Klavdia · 25.06.2013, 21:13

Народ, может я чего не понимаю, объясните, зачем тут формула Пика (при всём уважении) и всё остальное, когда, по-моему, очевидно, что под отрезком находится $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{int(x1+1)}^{intx2}int(Ai+B)$ целых и положительных чисел. Ну поднять это всё по у, чтобы осью х не прошило, кол-во целых чисел от этого не изменится.
И потом перебрать варианты по х1, х2, х3, у1, у2, у3, на предмет того, кто из них больше, кто меньше, чтобы с плюсом или с минусом поставить каждую из этих трёх сумм (по каждому отрезку) в общую сумму.

@helter · 26.06.2013, 11:26

Сообщение от Klavdia

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{int(x1+1)}^{intx2}int(Ai+B)$

А что означает эта запись?

@Klavdia · 26.06.2013, 11:38

у=Ax+B - прямая, на которой лежит отрезок, х1, х2, у1, у2 - координаты его концов. Подразумевается, что отрезок весь лежит в положительной области у, т.е. в алгоритме присутствует поднять всё на mod(min(y)), если, конечно у него есть отрицательные значения. int(x) - целая часть х.
В результате, это всё - есть количество натуральных чисел под отрезком.

@helter · 26.06.2013, 16:09

Подозреваю, своим способом вы раньше или позже пришли бы к формуле Пика. Только нужно действовать аккуратно: смотреть, какая сторона под какой находится (возможны, например, конфигурации Δ, ∇ и т. п.). Это с точки зрения математики. А с точки зрения вычислений тут ещё и цикл, в котором целые части считать. Работа с вещественными числами, это уже приближённые вычисления; а целая часть - разрывная функция, можно ли быть уверенным, что нигде не будет ошибки из-за округления?

Вместо геометрического анализа, циклов и приближённых вычислений можно просто посчитать по одной формуле в рамках целочисленной арифметики. Давайте скажем математикам спасибо.

@Klavdia · 26.06.2013, 16:15

Сообщение от helter

Давайте скажем математикам спасибо.

Это уж всенепременно скажем!

Новые блоги и статьи Все статьи Все блоги /
Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	Контроль уникальности заводского номера - вариант №2 Maks 24.03.2026 В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера - вариант №1 Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .

@katya 6 / 6 / 0 Регистрация: 21.03.2012 Сообщений: 184

	Опишите алгоритм, определяющий количество целочисленных точек, попавших внутрь треугольника 14.06.2013, 21:37. Показов 7173. Ответов 18 Метки нет (Все метки) помогите пожалуйста с решением! Даны координаты вершин треугольника на плоскости. Опишите алгоритм, определяющий количество целочисленных точек, попавших внутрь треугольника 0

@Cute 1077 / 658 / 68 Регистрация: 10.02.2011 Сообщений: 518
	15.06.2013, 00:22
	Сообщение было отмечено как решение Решение Вот программа, составленная в среде Mathcad (см. рис.): S(x1,y1,x2,y2,x3,y3) - функция, вычисляющая площадь треугольника по координатам его вершин $https://www.cyberforum.ru/cgi-bin/latex.cgi?({x}_{1},{y}_{1}), ({x}_{2},{y}_{2}), ({x}_{3},{y}_{3})$ ; gcd(a,b) - наибольший общий делитель чисел a и b. Миниатюры 4

@katya 6 / 6 / 0 Регистрация: 21.03.2012 Сообщений: 184
	16.06.2013, 13:25 [ТС]
	уважаемые программисты, помогите эту задачу сделать на паскале...пожалуйста 0

@katya 6 / 6 / 0 Регистрация: 21.03.2012 Сообщений: 184
	24.06.2013, 23:39 [ТС]
	@Cute, объясните пожалуйста, как задачу реализовать в паскале... 0

@katya 6 / 6 / 0 Регистрация: 21.03.2012 Сообщений: 184
	24.06.2013, 23:46 [ТС]
	очень жаль... 0

@helter 4528 / 3522 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	24.06.2013, 23:51
	Есть замечательная формула - формула Пика: S = N - B/2 - 1/2 где S - площадь выпуклого многоугольника с целочисленными вершинами, N - число принадлежащих ему целочисленных точек, B - число целочисленных точек точек на границе. Площадь треугольника находится по стандартной формуле аналитической геометрии. Если a = (a1, a2) и b = (b1, b2) - целочисленные точки, то на отрезке [a, b] лежит НОД(b1 - a1, b2 - a2) + 1 целочисленных точек. По-моему, это несложно реализовать на любом языке программирования. Правда, на паскале, наверно, придётся НОД отдельно писать. Но это пара строчек (алгоритм Евклида, рекурсия). 0

@katya 6 / 6 / 0 Регистрация: 21.03.2012 Сообщений: 184
	24.06.2013, 23:55 [ТС]
	если честно, то не понимаю как это реализовать в паскале.. 0

@ermolay 3451 / 2389 / 2135 Регистрация: 04.12.2011 Сообщений: 3,966
	25.06.2013, 00:11
	Количество целочисленных точек, попавших внутрь треугольника 0

@Denis123456789 43 / 43 / 21 Регистрация: 02.06.2013 Сообщений: 181
	25.06.2013, 01:05
	Я думаю надо сначала задать в программе уравнения сторон треугольника. Затем сравниваем координаты точек с границами области. По y: берем координату х точки, вставляем ее в уравнения сторон треугольника, находим какие из уравнений сторон дают минимальные и максимальные y, это будут границы области снизу и сверху соответственно. Если y точки меньше (равен) верхней границы и больше (равен) нижней границе, то по y условие выполняется. По x: берем теперь y точки и вставляем в уравнения сторон треугольника, далее аналогично (только теперь получаем x), только теперь это левая и правая граница. Если оба условия выполнены, то точка входит в треугольник. Но, наверное, криво написал 0

@Klavdia 135 / 112 / 13 Регистрация: 03.06.2013 Сообщений: 270
	25.06.2013, 21:13
	Народ, может я чего не понимаю, объясните, зачем тут формула Пика (при всём уважении) и всё остальное, когда, по-моему, очевидно, что под отрезком находится $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{int(x1+1)}^{intx2}int(Ai+B)$ целых и положительных чисел. Ну поднять это всё по у, чтобы осью х не прошило, кол-во целых чисел от этого не изменится. И потом перебрать варианты по х1, х2, х3, у1, у2, у3, на предмет того, кто из них больше, кто меньше, чтобы с плюсом или с минусом поставить каждую из этих трёх сумм (по каждому отрезку) в общую сумму. 0

@Klavdia 135 / 112 / 13 Регистрация: 03.06.2013 Сообщений: 270
	26.06.2013, 11:38
	у=Ax+B - прямая, на которой лежит отрезок, х1, х2, у1, у2 - координаты его концов. Подразумевается, что отрезок весь лежит в положительной области у, т.е. в алгоритме присутствует поднять всё на mod(min(y)), если, конечно у него есть отрицательные значения. int(x) - целая часть х. В результате, это всё - есть количество натуральных чисел под отрезком. 0

@helter 4528 / 3522 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	26.06.2013, 16:09
	Подозреваю, своим способом вы раньше или позже пришли бы к формуле Пика. Только нужно действовать аккуратно: смотреть, какая сторона под какой находится (возможны, например, конфигурации Δ, ∇ и т. п.). Это с точки зрения математики. А с точки зрения вычислений тут ещё и цикл, в котором целые части считать. Работа с вещественными числами, это уже приближённые вычисления; а целая часть - разрывная функция, можно ли быть уверенным, что нигде не будет ошибки из-за округления? Вместо геометрического анализа, циклов и приближённых вычислений можно просто посчитать по одной формуле в рамках целочисленной арифметики. Давайте скажем математикам спасибо. 1

Опишите алгоритм, определяющий количество целочисленных точек, попавших внутрь треугольника

Решение