Спрашивали на собеседовании...

← →
atruhin © (2006-10-04 22:58) [80]

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

← →
Ketmar © (2006-10-04 23:00) [81]

>[79] Чапаев(c) 4-Oct-2006, 22:57
>Кто угодно может, да не кто угодно вспомнит
>вовремя... ;-)
я эту задачу решал в досе и на TP5. %-)

← →
Чапаев © (2006-10-04 23:02) [82]

Ещё что-то из матана вспоминается... Берём угол, образованный вершиной, данной_точкой, следующей_вершиной. Суммируем так все углы. Если точка внутри, сумма равна 2*Pi, если снаружи -- 0.

Не помню сходу, как точно формулируется, но суть такая.

← →
atruhin © (2006-10-04 23:03) [83]

> [80] atruhin © (04.10.06 22:58)

Соврал в 4 пункте, нужно проверить угол пересечения, ограничивающей области и вектора:
Меньше 90 вышли на улицу
больше внутри многоугольника
равно 90 переходим к следующему вектору.
Ну и отдельно проверить на прямоугольник.

← →
atruhin © (2006-10-04 23:05) [84]

> [82] Чапаев © (04.10.06 23:02)

Это только для выпуклого

← →
Чапаев © (2006-10-04 23:07) [85]

Насколько я знаю, нет. Это вообще для любой фигуры верно, не только для многоугольника, только тогда приходится к интегралам и пределам переходить... ;-)

← →
Чапаев © (2006-10-04 23:07) [86]

Вообще в матане такая теоремка была для интегралов по контуру. Многоугольник -- частный случай.

← →
isasa © (2006-10-04 23:27) [87]

Джо © (04.10.06 22:29) [74]

Хитро. :)
Но в случае внутри, количество пересечений - нечетное?

Если выпуклая - обход по образуюшим векторам, если точка для всех с одной стороны - внутри ...

← →
noname_ (2006-10-05 09:39) [88]

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

← →
wal © (2006-10-05 09:54) [89]

> [88] noname_ (05.10.06 09:39)
Точка внутри "внутреннего" пятиугольника самопересекающейся пятиконечной звезды - внутри этой звезды или снаружи?

← →
clickmaker © (2006-10-05 10:04) [90]

> поменять две целочисленных переменных местами без использования
> третьей

asm
xchg a, b

?

← →
Иксик © (2006-10-05 10:11) [91]

> Джо © (04.10.06 20:30) [49]
> > [46] Иксик © (04.10.06 20:29)
> > А эта, оно возможно без виртуальной машины?
>
> Что, Lisp или RTTI? :)
> <Цитата>

RTTI

> > поменять две целочисленных переменных местами без использования
>
> > третьей

a=a+b
b=a-b
a=a-b

← →
Иксик © (2006-10-05 10:12) [92]

Модули забыл..

← →
noname_ (2006-10-05 10:16) [93]

2 wal [89]

это зависит от определения понятия "внутри" для самопересекающегося многоугольника

← →
clickmaker © (2006-10-05 10:19) [94]

> a=a+b
> b=a-b
> a=a-b

а если переполнение произойдет на 1-м шаге?

← →
Palladin © (2006-10-05 10:27) [95]

> а если переполнение произойдет на 1-м шаге?

монопенисуально

← →
Palladin © (2006-10-05 10:35) [96]

если конечно Range и/или Overflow checking не выставленно :)

← →
wal © (2006-10-05 11:05) [97]

> [93] noname_ (05.10.06 10:16)
Вот это первое, о чем бы я спросил Palladin"а, до того, как сел решать задачу, точнее второе, первое - для самопересекающихся тоже должно быть верное решение?

← →
Palladin © (2006-10-05 11:23) [98]

noname_
wal ©

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

задача дается в том виде в котором я ее написал и советую еще раз перечитать [27]

← →
wal © (2006-10-05 11:40) [99]

> [98] Palladin © (05.10.06 11:23)
Ну если вдруг случится так, что меня занесет в Ханты-Мансийск, то почему бы и нет :)

[27] перечитал, но ведь и подходы и методы зависят от этих уточнений. Или нет?

← →
Думкин © (2006-10-05 11:45) [100]

Понятие "внутри многоугольника" в общем случае - философское.

Можно ли оказаться внутри бутылки Клейна?

← →
Palladin © (2006-10-05 11:54) [101]

> wal © (05.10.06 11:40) [99]

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

← →
wal © (2006-10-05 12:16) [102]

> [101] Palladin © (05.10.06 11:54)
Да я все понимаю, сам собеседования иногда провожу :)

Всем:
А что вы считаете многоугоугольником? Лично мне при решении этой задачи, без уточняющих вопросов, удобнее было бы считать многоугольником замкнутую ломаную линию, а не часть плоскости, ограниченную этой линией, и проверить точку на принадлежность конечному числу отрезков ;)

С уважением.

← →
Думкин © (2006-10-05 12:30) [103]

> wal © (05.10.06 12:16) [102]

Многоугольник - упорядоченный набор точек, соединенных согласно этому порядку попарно отрезками.

← →
Prohodil Mimo © (2006-10-05 12:52) [104]

Джо © (06.10.04 22:29) [74]
http://www.unclejoe.ho.com.ua/img/poly.PNG

а если сделать в форме бублика? :о)

← →
Джо © (2006-10-05 16:57) [105]

> [104] Prohodil Mimo © (05.10.06 12:52)
> Джо © (06.10.04 22:29) [74]
> http://www.unclejoe.ho.com.ua/img/poly.PNG
>
> а если сделать в форме бублика? :о)

А PtInRegion из Win32, кстати, "бублики" тоже хорошо понимает :)

← →
Иксик © (2006-10-05 17:00) [106]

Так эта, возможно ли RTTI без виртуальной машины?

← →
Джо © (2006-10-05 17:02) [107]

> [106] Иксик © (05.10.06 17:00)
> Так эта, возможно ли RTTI без виртуальной машины?

Ну, так в Делфи же реализовано. :) Конечно, не в такой мере, как, скажем, в .Net, однако, достаточной для целого ряда задач.

>>clickmaker © (05.10.06 10:04) [90]

> > поменять две целочисленных переменных местами без использования
>
> > третьей
>
> asm
> xchg a, b
Если a и b переменные в памяти, то не прокатит, если мне не изменяет склероз.

Думкин © (05.10.06 12:30) [103]

Многоугольник - упорядоченный набор точек, соединенных согласно этому порядку попарно отрезками

То есть задача о принадлежности многоугольнику сводится к определению, есть ли указанная точка среди множества заданных? :)

> [110] Lamer@fools.ua © (05.10.06 17:37)
> >>clickmaker © (05.10.06 10:04) [90]
>
> > > поменять две целочисленных переменных местами без использования
>
> >
> > > третьей
> >
> > asm
> > xchg a, b
> Если a и b переменные в памяти, то не прокатит, если мне
> не изменяет склероз.

A := A+B;
B := A-B;
A := A-B;

:)

>[112] Джо(c) 5-Oct-2006, 17:47
> A := A+B;
> B := A-B;
> A := A-B;
фе.
procedure Exchange (var a, b: Integer); register; asm push ebx mov ebx,[eax] mov ecx,[edx] mov [eax],ecx mov [edx],ebx pop ebx end;

вот так пишут настоящие фрики! и не говорите мне, что регистры -- это тоже такие переменные. %-)

> поменять две целочисленных переменных местами без использования
> третьей

xor

> xchg a, b

Низачот! ;-) Нельзя выполнять операции над двумя операциями в памяти. А вот загрузить одну из них в регистр, а затем содержимое регистра с переменной поменять -- это да.

Ещё так можно:
A := A mod B; B := A mod B; A := A mod B;

> A := A mod B;B := A mod B;A := A mod B;

mod = xor :) Что-то меня глючит.

> Нельзя выполнять операции над двумя операциями в памяти.

Операндами, конечно.

> Джо © (05.10.06 17:47) [112]

Ох и тормозить будет :-) Операции с памятью всё-таки быстрее мат процессора, особенно если переменные вещественные.

Спрашивали на собеседовании... Найти похожие ветки