На сколько частей делят плоскость прямые

@freewrestler · Регистрация: 10.11.2011

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

Здравствуйте форумчане. Задали задачку, идеи есть, но проблема с реализацией. Помогите решить пожалуйста, если не трудно. Условие:
Даны N точек на плоскости. Проведем прямые через каждую пару точек. На сколько частей ненулевой площади эти прямые делят плоскость?
Формат входных данных:
В первой строке входного файла задано число N - количество точек (2 <= N <= 10). Следующие N строк содержат по два числа X[i] Y[i] - каждая через пробел, координаты i-ой точки (-100 <= X[i], Y[i] <= 100). Никакие две точки не совпадают, никакие три не лежат на одной прямой. Все числа во входном файле целые.
Формат выходных данных:
В первой строке выходного файла выведите P - количество частей, на которые полученные прямые делят плоскость.
Пример:
Ввод:
4
0 0
0 1
1 0
1 1
Вывод:
16

@freewrestler · 29.04.2014, 16:29 **[ТС]**

Может с идеей поделитесь?

@TenGen · 29.04.2014, 16:56

freewrestler, есть идея рассчитывать количество пересечений линий и по ним узнавать кол-во элементов: кол-во пересечений+2. Вроде такой принцип работает
http://gospodaretsva.com/urok-... rezka.html вот тут есть материал на эту тему

ValeryS · 29.04.2014, 17:11

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

есть идея рассчитывать количество пересечений линий и по ним узнавать кол-во элементов: кол-во пересечений+2.

возьмем две линии
параллельные кол-во пересечений =0 частей 3
пересекающиеся кол-во пересечений =1 частей 4
возьмем три линии
параллельные кол-во пересечений =0 частей 4
две параллельные одна пересекает кол-во пересечений =2 частей 6
все пересекаются кол-во пересечений =3 частей 7

так что не подходит
нужно учитывать еще и количество линий
я так вижу
изначально есть одна часть(сама плоскость)
т.е 1+ количество линий + количество пересечений
но дальше трех эту формулу не проверял

@TenGen · 29.04.2014, 17:16

ValeryS, мой косяк, я считал исходя из мысли, что прямые соединяются друг с другом

@freewrestler · 29.04.2014, 17:50 **[ТС]**

ValeryS, а что если какая-та точка является точкой пересечения нескольких прямых ?

ValeryS · 29.04.2014, 17:58

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

@freewrestler · 30.04.2014, 16:12 **[ТС]**

чет трудноватая ((. Кажется тут не только нужно вывести формулу, а также все зависит от самих координат(

@Alex5 · 30.04.2014, 17:03

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

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

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

изначально есть одна часть(сама плоскость)
т.е 1+ количество линий + количество пересечений

Вот обоснование утверждения ValeryS.
Пусть проведено несколько прямых. Проводим ещё одну прямую. m точек пересечения делят новую прямую на m+1 интервал.
Каждый интервал делит некоторую область на две части. Значит, количество областей увеличивается на m+1.
(При этом число точек увеличивается на m, число прямых увеличивается на 1.)

@freewrestler · 30.04.2014, 18:46 **[ТС]**

Alex5, Видим, что:
Линий: 6
Точек пересечения: 5
Итого: 1 + 6 + 5 = 12
А разделено на 16 частей.

@intern · 30.04.2014, 19:08

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

Проведем прямые через каждую пару точек.

А линий то 10, просто некоторые совпадают

@freewrestler · 30.04.2014, 19:15 **[ТС]**

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

А линий то 10, просто некоторые совпадают

чего чего? сколько линий?

@intern · 30.04.2014, 19:21

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

Проведем прямые через каждую пару точек

AB, BC, AC

@freewrestler · 30.04.2014, 19:35 **[ТС]**

4 точки, с координатами:
(0; 0), (1; 0), (0; 1), (1; 1)
6 линий получится. Посчитай еще раз.

@kamre · 30.04.2014, 19:56

Есть же условие:

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

никакие три не лежат на одной прямой

@freewrestler · 30.04.2014, 19:58 **[ТС]**

kamre, вы мне или intern-у ?

@Alex5 · 30.04.2014, 20:09

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

Alex5, Видим, что:
Линий: 6
Точек пересечения: 5
Итого: 1 + 6 + 5 = 12
А разделено на 16 частей.

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

@freewrestler · 30.04.2014, 20:27 **[ТС]**

А вот в чем дело, спасибо) А как быть, когда точка является точкой пересечения >2 прямых ?

@Toshkarik · 30.04.2014, 20:49

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

никакие три не лежат на одной прямой

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

Никакие две точки не совпадают

Это будет противоречить одному из условий. Поэтому через одну точку проходит не больше 2 прямых.

@freewrestler · 30.04.2014, 20:54 **[ТС]**

Вы наверное не так поняли условие. "Никакие две точки не совпадают", т.е при в воде координаты всех точек различны, т.е к примеру там никогда не встретятся 2 точки с координатами (0;1) и (0;1).
"Никакие три не лежат на одной прямой" - т.е при вводе не будет таких точек(к примеру): (0;0), (1;1), (2;2) - т.к эти точки лежат на одной прямой.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126

	На сколько частей делят плоскость прямые 26.04.2014, 18:22. Показов 17844. Ответов 36 Метки нет (Все метки) Здравствуйте форумчане. Задали задачку, идеи есть, но проблема с реализацией. Помогите решить пожалуйста, если не трудно. Условие: Даны N точек на плоскости. Проведем прямые через каждую пару точек. На сколько частей ненулевой площади эти прямые делят плоскость? Формат входных данных: В первой строке входного файла задано число N - количество точек (2 <= N <= 10). Следующие N строк содержат по два числа X[i] Y[i] - каждая через пробел, координаты i-ой точки (-100 <= X[i], Y[i] <= 100). Никакие две точки не совпадают, никакие три не лежат на одной прямой. Все числа во входном файле целые. Формат выходных данных: В первой строке выходного файла выведите P - количество частей, на которые полученные прямые делят плоскость. Пример: Ввод: 4 0 0 0 1 1 0 1 1 Вывод: 16 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	29.04.2014, 16:29 [ТС]
	Может с идеей поделитесь? 0

@TenGen Будущее рядом 101 / 100 / 48 Регистрация: 06.03.2014 Сообщений: 342
	29.04.2014, 16:56
	freewrestler, есть идея рассчитывать количество пересечений линий и по ним узнавать кол-во элементов: кол-во пересечений+2. Вроде такой принцип работает http://gospodaretsva.com/urok-... rezka.html вот тут есть материал на эту тему 1

@TenGen Будущее рядом 101 / 100 / 48 Регистрация: 06.03.2014 Сообщений: 342
	29.04.2014, 17:16
	ValeryS, мой косяк, я считал исходя из мысли, что прямые соединяются друг с другом 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	29.04.2014, 17:50 [ТС]
	ValeryS, а что если какая-та точка является точкой пересечения нескольких прямых ? 0

ValeryS Модератор 8978 / 6744 / 921 Регистрация: 14.02.2011 Сообщений: 23,854
	29.04.2014, 17:58
	freewrestler, ну так нарисуй и посмотри выведи закономерность я эту формулу прямо сейчас вывел, нарисовав несколько линий вообще этим целая наука занимается, по моему, топология 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	30.04.2014, 16:12 [ТС]
	чет трудноватая ((. Кажется тут не только нужно вывести формулу, а также все зависит от самих координат( 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	30.04.2014, 18:46 [ТС]
	Alex5, Видим, что: Линий: 6 Точек пересечения: 5 Итого: 1 + 6 + 5 = 12 А разделено на 16 частей. Миниатюры 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	30.04.2014, 19:35 [ТС]
	4 точки, с координатами: (0; 0), (1; 0), (0; 1), (1; 1) 6 линий получится. Посчитай еще раз. 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	30.04.2014, 19:58 [ТС]
	kamre, вы мне или intern-у ? 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	30.04.2014, 20:27 [ТС]
	А вот в чем дело, спасибо) А как быть, когда точка является точкой пересечения >2 прямых ? 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	30.04.2014, 20:54 [ТС]
	Вы наверное не так поняли условие. "Никакие две точки не совпадают", т.е при в воде координаты всех точек различны, т.е к примеру там никогда не встретятся 2 точки с координатами (0;1) и (0;1). "Никакие три не лежат на одной прямой" - т.е при вводе не будет таких точек(к примеру): (0;0), (1;1), (2;2) - т.к эти точки лежат на одной прямой. 0