Problematic problem

[Boyov]

Вот задача:



На contest-е её никто не решил.
Может вы сможете


P.S. sory за jpg, просто Я copy-paste-ил из pdf.


Regards
A.

P.S. Solution is available

[greka]

plz skonvertiruy JPG v Grayscale JPEG...

razmer slishkom velik.

[Boyov]

Originally posted by Greco El
plz skonvertiruy JPG v Grayscale JPEG...

razmer slishkom velik.

Sorry, но у меня тока mspaint.

[greka]

esli N ob'ektov pokryvayut "2*Pi" uglov, to gde problema-to ?

Vot tebe JPEG s resheniem:

[greka]

ur-e pryamoy pod zadannym uglom ne pomnyu, seychas vyvedem:

(x-x1) / (x2-x1) = (y-y1) / (y2-y1), where x1, x2, y1, x2 == const

let
x1 = 0
y1 = 0

then
x/x2 = y/y2,
i.e.


y = x*(y2/x2) = x * tg(Alfa)

[nm]

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

1. в условии сказано - координаты источников даны
2. там же сказано - источники света не могут быть расположены в одной точке



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

[greka]

tak, ne mogu skachat' etot JPEG, chotb posmotret' usloviya..

esli, govorish', tochki tebe uje zadany (a oni zadany mogut byt' na 1 pryamoy..

tebe ne slojno perepechatat' toka tekst syuda ?

[greka]

naskoka ya pomyu, tamnim usloviem bylo:

luchi ne perekryvayutsa.
?

[greka]

наверное, так:

1. через любые 2 точки можно провести прямую (L1)
2. это означает, что строим 2 источника света так, чтоб они дополняли друг друга, как на JPEG-e.

И так - для всех остальных точек - берется одна из уже рассчитанных и одна из "available" - и делается пересчет "линии синхронизации" L2

Задача сводится к тому, чтоб найти комбинацию, когда все поространство покрыто и через все точки проведены "линии синхронизации".
Для этого и давалось 2 минуты максимум

как тебе идея, nm?

[greka]

а о найденном решении можно узнать так:
суммируем углы синхронизации:

Angel(L1)+Angel(L2)+... == 360 (?)

/точнее - не углы, а (угол/2), что ли... /
Как углы прямой расчитывать - мы знаем.

[nm]

tot zhe jpg s zadachkoj lezhit uzhe na
http://docs.nothing.am/xndir.jpg

[nm]

Originally posted by Greco El
naskoka ya pomyu, tamnim usloviem bylo:

luchi ne perekryvayutsa.
?

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

[Obelix]

Почему то мне кажется, что в окончательной конфигурации лучи должны быть друг-другу паралельны - точнее луч каждого источника должен быть паралелен лучу другого источника.

[Фиби]

Итак, от имено тов. Агабабова:

задача на самом деле достаточно сложна.
Тут http://neerc.ifmo.ru/regional/problems/archive.rar лежат решения жюри для всех задач этого соревнования. Дано для каждой задачи несколько решений. Все решения паскаль.
Далее, для данной задачи есть специальный doc файл, где дано ее решение (мат обоснование). Итак, 3 теоремы, 2 леммы и одно следствие... нипадецки, однако! Совсем не удивительно, что ее никто не решил

[Фиби]

Originally posted by Obelix
Почему то мне кажется, что в окончательной конфигурации лучи должны быть друг-другу паралельны - точнее луч каждого источника должен быть паралелен лучу другого источника.

И это тоже верно. Теорема X из док файла, именно это и указывает (косвенным образом). Но этого черезчур мало для того, чтобы решить эту задачу