Разница областей

[Evgeniy Sklyarevskiy]

На плоскости проведено n прямых, которые разбивают ее на области. Области закрашиваются в шахматном порядке. Спрашивается, для заданного числа n, какова максимально-возможная разность между числом черных и числом белых областей? (Из задач Арнольда)

Сорри, картинка великовата.. для наглядности.

http://www.assembla.com/spaces/arnold_problem/documents/cKxciQ_2ur3ARweJe5afGb/download/A%E2%80%8B%E2%80%8B%E2%80%8B(%E2%80%8B%E2%80%8B%E2 %80%8B9,%E2%80%8B%E2%80%8B%E2%80%8B0%E2%80%8B)%E2% 80%8B%E2%80%8B%E2%80%8B=%E2%80%8B%E2%80%8B%E2%80%8 B14%E2%80%8B%E2%80%8B%E2%80%8B

[Shuhrat Ismailov]

Спрашивается, для заданного числа n, какова максимально-возможная разность между числом черных и числом белых областей? (Из задач Арнольда)
Я слышал, что данная задача еще не решена. Или уже решили?

[Evgeniy Sklyarevskiy]

Я слышал, что данная задача еще не решена. Или уже решили?

Нет, есть попытки решения и обсуждения здесь http://www.gamedev.ru/flame/forum/?id=131943 и здесь http://written.ru/blog/2008/03/09/Problem
Сложная задача конечно, думаю форумчане смогут "покусать" ее с разных сторон.

[Nadir Zaitov]

Предлагаю написать програмку, которая:

1. По заданным уравнениям кривых нарежует плоскость на набор многоугольников. (Ввод: прямые на плоскости в форме {числа A, B и С из уавнение прямой Аx+By=C}, вывод: многоугольники {номер многоугольника; число углов; {координаты (X,Y) углов многоугольника};

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

3. Для непрограммистов доказать, что раскраска такой карты стран (созданной пересечением 7 прямых) в 2 цвета без общих границ в 1 цвет возможна.

[Evgeniy Sklyarevskiy]

1. По заданным уравнениям кривых нарежует плоскость на набор многоугольников. (Ввод: прямые на плоскости в форме {числа A, B и С из уавнение прямой Аx+By=C}, вывод: многоугольники {номер многоугольника; число углов; {координаты (X,Y) углов многоугольника}; Могу найти все точки пересечений :-0)
Но как из них построить многоугольники не могу сообразить. Можно, например, идти вдоль одной линии, рассматривая все пересечения и порождаемые ими многоугольники. Но как определить, какая точка является вершиной рассматриваемого многоугольника, а какая нет?

[Nadir Zaitov]

Но как из них построить многоугольники не могу сообразить.Есть 2 типа многоугольников: конечные, бесконечные.

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

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

[николай москвитин]

Но как из них построить многоугольники не могу сообразить.Есть 2 типа многоугольников: конечные, бесконечные.

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

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

А можно попробовать действовать по-другому ? Я предлагаю как-то привязать известную комбинаторную формулу для максимального количества частей, на которые разбивают данную плоскость n прямых к задаче. Вот эта формула: (n^2+n+2)/2
Может быть, можно как-то посчитать через эту формулу?

[николай москвитин]

На плоскости проведено n прямых, которые разбивают ее на области. Области закрашиваются в шахматном порядке. Спрашивается, для заданного числа n, какова максимально-возможная разность между числом черных и числом белых областей? (Из задач Арнольда)

Сорри, картинка великовата.. для наглядности.

http://www.assembla.com/spaces/arnold_problem/documents/cKxciQ_2ur3ARweJe5afGb/download/A%E2%80%8B%E2%80%8B%E2%80%8B(%E2%80%8B%E2%80%8B%E2 %80%8B9,%E2%80%8B%E2%80%8B%E2%80%8B0%E2%80%8B)%E2% 80%8B%E2%80%8B%E2%80%8B=%E2%80%8B%E2%80%8B%E2%80%8 B14%E2%80%8B%E2%80%8B%E2%80%8B
для наглядности

А почему некоторые области, ограниченные только двумя прямыми, имеют внутри и чёрный, и белый цвета внутри? Ведь если это новые прямые, то они отсекут ещё области, а если прямых ровно n, такое невозможно.

[николай москвитин]

Я слышал, что данная задача еще не решена. Или уже решили?

Нет, есть попытки решения и обсуждения здесь http://www.gamedev.ru/flame/forum/?id=131943 и здесь http://written.ru/blog/2008/03/09/Problem
Сложная задача конечно, думаю форумчане смогут "покусать" ее с разных сторон.
Сложная задача конечно

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

[Makhmud]

я уж подумал по названию темы, что вы решили найти разницу областей Узбекистана