Вычисление площади односвязной прямоугольной фигуры по координатам ее вершин

@bob1957a · Регистрация: 24.07.2017

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

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

@woldemas · 12.09.2017, 18:44

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

0 4 4 3 0 3 0 0

А что это?
Это вроде не прямоугольник...

@Skjame · 12.09.2017, 18:45

а почему вы решили что все углы прямоугольные?
woldemas написал что он предполагает так, но а что если там только 1 прямой угол, тогда точек может быть 100к+

@woldemas · 12.09.2017, 18:48

Skjame, Я вообще предполагал, что это такая ступенчатая фигура с большим числом сторон, но вроде все пришли к выводу что это прямоугольник, для прямоугольника-то просто должно быть

@bormant · 12.09.2017, 18:58

С циклами, так с циклами:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int sqr(int x) { return x*x; }
int main()
{
    int x[3], y[3], d[4], f=0;
    printf("ax ay bx by cx cy: ");
    for (int i=0; i<3; ++i) scanf(" %d %d", &x[i], &y[i]);
    for (int i=0; i<4; ++i) d[i]=sqr(x[i%3]-x[(i+1)%3])+sqr(y[i%3]-y[(i+1)%3]);
    for (int i=0; i<4; ++i)
        if (d[i]+d[(i+1)%3]==d[(i+2)%3]) {
            printf("%.0f\n",sqrt(d[i]*d[(i+1)%3])); f=1; break; }
    if (!f) printf("нет прямого угла\n");
    return 0;
}

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

Это вроде не прямоугольник...

точно.

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

почему вы решили что все углы прямоугольные?

В условии прямоугольная фигура. Пожалуй, по аналогии с прямоугольным треугольником, действительно, достаточно только одного прямого угла. Суть вопроса в этом?

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

@woldemas · 12.09.2017, 19:04

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

точно

Вроде проверить, что это прямоугольник цели не было.

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

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

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

@bormant · 12.09.2017, 19:11

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

Вершины могут немонотонно располагаться (типа, с загибами назад) и сортировка ничего не даст

Так мы в порядке возрастания угла, почему не даст? А, вижу, того, что фигура выпуклая, никто не обещал.

Другое дело, как быть, если прямых углов окажется несколько (кандидаты -- красные), или угол внешний 90, а не внутренний...

@woldemas · 12.09.2017, 19:13

Вообще наличие одного прямого угла условие почти бесполезное, мне кажется.

@bormant · 12.09.2017, 19:14

С другой стороны, вершины в произвольном порядке заданы, как понять, о какой конкретно фигуре речь?

@woldemas · 12.09.2017, 19:26

Немонотонно это вот так:

Вычисление площади односвязной прямоугольной фигуры по координатам ее вершин

При сортировке вершина A будет опережать B.

@easybudda · 12.09.2017, 20:47

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

а почему вы решили что все углы прямоугольные?

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

Все её углы прямые

Как вариант - найти расстояния от первой точки до остальных. Самое длинное - диагональ, два оставшихся перемножить.

@bob1957a · 12.09.2017, 22:13 **[ТС]**

на плоскости, координаты целыми числами задаются

Добавлено через 1 минуту

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

bormant, координаты в случайном порядке задаются, нужно вначале ещё определить где Bx By

нет, в порядке (X Y)

@bob1957a · 12.09.2017, 22:22 **[ТС]**

Уточняю условие на "живом примере". См вложение.

@bormant · 12.09.2017, 22:29

Ну и почему в условии сразу не написано, что стороны параллельны осям координат?

@bob1957a · 13.09.2017, 00:08 **[ТС]**

Могут быть НЕпараллельны, просто пример неудачный привел.

@woldemas · 13.09.2017, 04:16

bob1957a, я так и понял изначально, но меня сбили с толку, я писал уже в сторону чего вам смотреть:

Если я правильно понял, это не слишком простая задача. У сторон получается только два направления: прямое и ортогональное. Нужно перемещаясь по точкам вдоль одного из направлений считать площадь прямоугольника отсекаемого прямой параллельной другому направлению, проходящей через текущую точку. Это что-то из так называемых алгоритмов "заметания" надо использовать.

@easybudda · 13.09.2017, 05:42

Тогда всё веселее, я почему-то был уверен, что речь о прямоугольнике с 4 заданными вершинами произвольно повёрнутом на плоскости. А если так - забавный метод "Монте-Карло" можно попробовать. Только нужно будет точно описать, при каких условиях точка в фигуру попадает...

@woldemas · 13.09.2017, 10:29

Решать задачу надо для выравненного по осям. Из произвольного его можно получить проекцией на крайние из лучей, направленные из минимальной по всем координатам точке к остальным точкам.
За nlog(n) можно найти все стороны многоугольника в виде индексированных ребер (двумя лексикографическими сортировками: сначала x-y - получаем вертикальные ребра, потом y-x - получаем горизонтальные ребра) и построить последовательность точек многоугольника.
А дальше уже вычислять площадь произвольного невыпуклого многоугольника.
Может быть есть более простой метод.

@bormant · 13.09.2017, 11:10

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

Из произвольного его можно получить

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

@woldemas · 13.09.2017, 12:20

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

из произвольного еще надо умудриться собрать

Не надо собирать на первом этапе.
Сначала можно найти направления сторон (крайние два луча из минимальной, например по x, точки к остальным), потом зная эти новые оси все точки без учета порядка поворачиваем. В этих новых координатах стороны будут только вертикальными и горизонтальными.

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

количество возможных многоугольников легко может оказаться больше одного

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

@Skjame · 13.09.2017, 12:41

bob1957a, то что x y идут в таком порядке - это очевидно, ведь именно (x;y) и есть описание точки. Имеется в виду, что может быть (x0;y0) (x3;y3) (x1;y1) (x2;y2) и т.д.

если сейчас выясниться, что и точки не перепутаны, то это вообще трындец будет)))

Новые блоги и статьи Все статьи Все блоги /
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .

@bob1957a 0 / 0 / 0 Регистрация: 24.07.2017 Сообщений: 43

	Вычисление площади односвязной прямоугольной фигуры по координатам ее вершин 11.09.2017, 22:25. Показов 6132. Ответов 42 Метки координаты, площадь, прямоугольной (Все метки) Написать программу, вычисляющую площадь односвязной прямоугольной фигуры, заданной перечислением пар целочисленных координат её вершин в произвольном порядке. 0

@Skjame 86 / 45 / 11 Регистрация: 20.12.2010 Сообщений: 217 Записей в блоге: 1
	12.09.2017, 18:45
	а почему вы решили что все углы прямоугольные? woldemas написал что он предполагает так, но а что если там только 1 прямой угол, тогда точек может быть 100к+ 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	12.09.2017, 18:48
	Skjame, Я вообще предполагал, что это такая ступенчатая фигура с большим числом сторон, но вроде все пришли к выводу что это прямоугольник, для прямоугольника-то просто должно быть 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	12.09.2017, 19:13
	Вообще наличие одного прямого угла условие почти бесполезное, мне кажется. 0

@bormant Модератор 7818 / 4637 / 2837 Регистрация: 22.11.2013 Сообщений: 13,159 Записей в блоге: 1
	12.09.2017, 19:14
	С другой стороны, вершины в произвольном порядке заданы, как понять, о какой конкретно фигуре речь? 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	12.09.2017, 19:26
	Немонотонно это вот так: При сортировке вершина A будет опережать B. 0

@bob1957a 0 / 0 / 0 Регистрация: 24.07.2017 Сообщений: 43
	12.09.2017, 22:22 [ТС]
	Уточняю условие на "живом примере". См вложение. Миниатюры 0

@bormant Модератор 7818 / 4637 / 2837 Регистрация: 22.11.2013 Сообщений: 13,159 Записей в блоге: 1
	12.09.2017, 22:29
	Ну и почему в условии сразу не написано, что стороны параллельны осям координат? 0

@bob1957a 0 / 0 / 0 Регистрация: 24.07.2017 Сообщений: 43
	13.09.2017, 00:08 [ТС]
	Могут быть НЕпараллельны, просто пример неудачный привел. 0

@easybudda Модератор 12843 / 7592 / 1766 Регистрация: 25.07.2009 Сообщений: 13,981
	13.09.2017, 05:42
	Тогда всё веселее, я почему-то был уверен, что речь о прямоугольнике с 4 заданными вершинами произвольно повёрнутом на плоскости. А если так - забавный метод "Монте-Карло" можно попробовать. Только нужно будет точно описать, при каких условиях точка в фигуру попадает... 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	13.09.2017, 10:29
	Решать задачу надо для выравненного по осям. Из произвольного его можно получить проекцией на крайние из лучей, направленные из минимальной по всем координатам точке к остальным точкам. За nlog(n) можно найти все стороны многоугольника в виде индексированных ребер (двумя лексикографическими сортировками: сначала x-y - получаем вертикальные ребра, потом y-x - получаем горизонтальные ребра) и построить последовательность точек многоугольника. А дальше уже вычислять площадь произвольного невыпуклого многоугольника. Может быть есть более простой метод. 0

@Skjame 86 / 45 / 11 Регистрация: 20.12.2010 Сообщений: 217 Записей в блоге: 1
	13.09.2017, 12:41
	bob1957a, то что x y идут в таком порядке - это очевидно, ведь именно (x;y) и есть описание точки. Имеется в виду, что может быть (x0;y0) (x3;y3) (x1;y1) (x2;y2) и т.д. если сейчас выясниться, что и точки не перепутаны, то это вообще трындец будет))) 0