Форум программистов, компьютерный форум, киберфорум
Геометрия
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.99/68: Рейтинг темы: голосов - 68, средняя оценка - 4.99
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
1

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

26.04.2014, 18:22. Показов 13802. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.04.2014, 18:22
Ответы с готовыми решениями:

На сколько на сколько частей делят треугольник...
На одной из боковых сторон треугольника взято n точек, на второй - m точек. Каждая вершина при...

На сколько частей делится плоскость?
На сколько частей делить площадь 7ми прямых общего пложения?

Две прямые и плоскость
Всем доброго времени. Такая беда. Нужно построить плоскость, проходящею через прямые L(1):...

Прямые разбивают плоскость на полосы
Прямые разбивают плоскость на полосы ширины 7. Определить вероятность того, что отрезок длины 1,...

36
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
29.04.2014, 16:29  [ТС] 2
Может с идеей поделитесь?
0
Будущее рядом
101 / 100 / 48
Регистрация: 06.03.2014
Сообщений: 342
29.04.2014, 16:56 3
freewrestler, есть идея рассчитывать количество пересечений линий и по ним узнавать кол-во элементов: кол-во пересечений+2. Вроде такой принцип работает
http://gospodaretsva.com/urok-... rezka.html вот тут есть материал на эту тему
1
Модератор
Эксперт по электронике
8569 / 6385 / 859
Регистрация: 14.02.2011
Сообщений: 22,215
29.04.2014, 17:11 4
Цитата Сообщение от TenGen Посмотреть сообщение
есть идея рассчитывать количество пересечений линий и по ним узнавать кол-во элементов: кол-во пересечений+2.
возьмем две линии
параллельные кол-во пересечений =0 частей 3
пересекающиеся кол-во пересечений =1 частей 4
возьмем три линии
параллельные кол-во пересечений =0 частей 4
две параллельные одна пересекает кол-во пересечений =2 частей 6
все пересекаются кол-во пересечений =3 частей 7

так что не подходит
нужно учитывать еще и количество линий
я так вижу
изначально есть одна часть(сама плоскость)
т.е 1+ количество линий + количество пересечений
но дальше трех эту формулу не проверял
0
Будущее рядом
101 / 100 / 48
Регистрация: 06.03.2014
Сообщений: 342
29.04.2014, 17:16 5
ValeryS, мой косяк, я считал исходя из мысли, что прямые соединяются друг с другом
0
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
29.04.2014, 17:50  [ТС] 6
ValeryS, а что если какая-та точка является точкой пересечения нескольких прямых ?
0
Модератор
Эксперт по электронике
8569 / 6385 / 859
Регистрация: 14.02.2011
Сообщений: 22,215
29.04.2014, 17:58 7
freewrestler,
ну так нарисуй и посмотри выведи закономерность
я эту формулу прямо сейчас вывел, нарисовав несколько линий
вообще этим целая наука занимается, по моему, топология
0
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
30.04.2014, 16:12  [ТС] 8
чет трудноватая ((. Кажется тут не только нужно вывести формулу, а также все зависит от самих координат(
0
1129 / 788 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
30.04.2014, 17:03 9
Цитата Сообщение от freewrestler Посмотреть сообщение
На сколько частей ненулевой площади эти прямые делят плоскость?
Цитата Сообщение от ValeryS Посмотреть сообщение
изначально есть одна часть(сама плоскость)
т.е 1+ количество линий + количество пересечений
Вот обоснование утверждения ValeryS.
Пусть проведено несколько прямых. Проводим ещё одну прямую. m точек пересечения делят новую прямую на m+1 интервал.
Каждый интервал делит некоторую область на две части. Значит, количество областей увеличивается на m+1.
(При этом число точек увеличивается на m, число прямых увеличивается на 1.)
Миниатюры
На сколько частей делят плоскость прямые  
0
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
30.04.2014, 18:46  [ТС] 10
Alex5, Видим, что:
Линий: 6
Точек пересечения: 5
Итого: 1 + 6 + 5 = 12
А разделено на 16 частей.
Миниатюры
На сколько частей делят плоскость прямые  
0
15 / 15 / 8
Регистрация: 30.03.2014
Сообщений: 75
30.04.2014, 19:08 11
Цитата Сообщение от freewrestler Посмотреть сообщение
Проведем прямые через каждую пару точек.
А линий то 10, просто некоторые совпадают
0
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
30.04.2014, 19:15  [ТС] 12
Цитата Сообщение от intern Посмотреть сообщение
А линий то 10, просто некоторые совпадают
чего чего? сколько линий?
0
15 / 15 / 8
Регистрация: 30.03.2014
Сообщений: 75
30.04.2014, 19:21 13
Цитата Сообщение от freewrestler Посмотреть сообщение
Проведем прямые через каждую пару точек
AB, BC, AC
Миниатюры
На сколько частей делят плоскость прямые  
0
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
30.04.2014, 19:35  [ТС] 14
4 точки, с координатами:
(0; 0), (1; 0), (0; 1), (1; 1)
6 линий получится. Посчитай еще раз.
0
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
30.04.2014, 19:56 15
Есть же условие:
Цитата Сообщение от freewrestler Посмотреть сообщение
никакие три не лежат на одной прямой
0
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
30.04.2014, 19:58  [ТС] 16
kamre, вы мне или intern-у ?
0
1129 / 788 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
30.04.2014, 20:09 17
Цитата Сообщение от freewrestler Посмотреть сообщение
Alex5, Видим, что:
Линий: 6
Точек пересечения: 5
Итого: 1 + 6 + 5 = 12
А разделено на 16 частей.
Да, рассуждение из сообщения #9 верно для случая, когда нет точек, принадлежащих более чем двум прямым.
1
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
30.04.2014, 20:27  [ТС] 18
А вот в чем дело, спасибо) А как быть, когда точка является точкой пересечения >2 прямых ?
0
1174 / 887 / 94
Регистрация: 03.08.2011
Сообщений: 2,457
30.04.2014, 20:49 19
Цитата Сообщение от freewrestler Посмотреть сообщение
никакие три не лежат на одной прямой
Цитата Сообщение от freewrestler Посмотреть сообщение
Никакие две точки не совпадают
Это будет противоречить одному из условий. Поэтому через одну точку проходит не больше 2 прямых.
0
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
30.04.2014, 20:54  [ТС] 20
Вы наверное не так поняли условие. "Никакие две точки не совпадают", т.е при в воде координаты всех точек различны, т.е к примеру там никогда не встретятся 2 точки с координатами (0;1) и (0;1).
"Никакие три не лежат на одной прямой" - т.е при вводе не будет таких точек(к примеру): (0;0), (1;1), (2;2) - т.к эти точки лежат на одной прямой.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.04.2014, 20:54

Построить плоскость, проходящую через прямые
Всем привет Задание: построить плоскость, проходящею через прямые l1= (x/1)=((y-1)/1)=(z/1) and...

На сколько частей и как нужно разделить отрезок, чтобы произведение длин частей было максимальным
Помогите написать вот такую программу. Не могу ничего придумать. Может методом перебора или еще...

Изобразить все используемые в задании объекты (прямые, плоскость, нормаль к плоскости)
Задание: Даны канонические уравнения двух прямых в пространстве. ...

Вычислить, на какое наибольшее количество частей могут разбить плоскость N окружностей
Окружности - 2 2 окружности разбивают плоскость максимум на 4 части. А на какое наибольшее...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru