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

@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) и т.д.

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

Новые блоги и статьи Все статьи Все блоги /
Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .

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

	Вычисление площади односвязной прямоугольной фигуры по координатам ее вершин 11.09.2017, 22:25. Показов 6023. Ответов 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,980
	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