Сообщений в теме: 193

[Havoc]

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

Вы лучше дайте хороший алгоритм для выпуклого

ПС: Деление многоугольника прямой на 2 равных по площади части - как бы вы это сделали?

Вот что я придумал.

Начнем с выпуклого: допустим, нам необходимо разделить его на 2 равные по площади части линией, параллельно оси х.
Проводим через каждую вершину прямую, параллельную оси х, таким образом разделив многоугольник на множество простых фигур, каждая из которых будет являть либо треугольником, либо трапецией.
Найти площадь каждой из этих фигур тривиально.
Затем начинаем двигаться с двух сторон, суммируя площади, и находим фигуру, обладающую такой площадью, что если прибавить ее к сумме площадей фигур ниже нее, эта сумма станет больше суммы площадей фигур выше нее, а если прибавить ее к сумме площадей фигур выше нее, эта сумма станет больше суммы площадей фигур ниже нее.
Затем следует разделить ее линией, параллельной оси х на две части так, чтобы S ниж. части + сумма S нижних фигур = S верхней части + сумма S верхних фигур. Эту задачу я пока не решил, но решу, вечером, когда время будет.

Вот иллюстрация:


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



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

1) для выпуклого, тупо взять центр найденной срединной трапеции.
2) для невыпуклого, найти среди фигур разреза такую же срединную фигуру и взять ее центр.

P.S. А вот еще пара идей конечно, это все будет не так точно, как если найти точно точку пересечения двух разделяющих прямых:

1) для выпуклого:
мы находим разрез по х, находим разрез по у.
Эти 4 прямые образуют прямоугольник. Берем его центр.

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

Если считать задачу разделения напополам по площади решенной, а она 100% решаема, то вышеупомянутой точкой будет не центр прямоугольника, а точка пересечения разделяющих прямых.

Сообщение отредактировал Havoc: 24.12.2009, 10:41:47

[yedyge]

Плохо. Не лучше, чем вариант с деревом в плане трудоемкости.
...
Тоже плохо, потому что сложно - стрельба из пушки по воробьям. Еще и невероятно медленно.

пишите ТЗ. то, что вы наформулировали вполне нормально решается данными методами, которые, кстати, наглядны, просты и гарантируют верный результат.

Для простоты считать ресурсы компьютера неограниченными

что я воспринимаю как "предварительные вычисления позволительны в любом объёме".
впрочем вычисления основного этапа тоже легко выполнимы.

со словарём согласно известному ТЗ делаете так:

select d.dictionary word, i.input_word
from input_table i
full outer join dictionary_table d on i.input_word = d.dictionary_word
where d.dictionary_word is null (или is not null)

с многоугольниками операция нахождения центра производится во время его создания, и хранится в описании многоугольника, так что в рантайме поиск центра сводится к чтению свойства объекта.

Сообщение отредактировал yedyge: 24.12.2009, 12:56:55

[Visual1]

И где тут проверка мыслительных способностей кандидата?

кого хотят - того и набирают

Это ответ не на мой вопрос. Вот не ожидал такой манеры от вас.

[yedyge]

Это ответ не на мой вопрос. Вот не ожидал такой манеры от вас.

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

если бы он спросил "как интервьюировать", я бы ответил иначе. но он занимается тем, что просто заявил, что ведёт собеседование именно так и отвергает чужие точки зрения. и тоже имеет право.

на что я имею право вам намекнуть, что "он сам себе буратино"

[Visual1]

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

если бы он спросил "как интервьюировать", я бы ответил иначе. но он занимается тем, что просто заявил, что ведёт собеседование именно так и отвергает чужие точки зрения. и тоже имеет право.

на что я имею право вам намекнуть, что "он сам себе буратино"

Да я и без ваших намеков и разъяснений ваших прав это понимаю. Я задавал г-ну dzid'y свой вопрос, а от вас ответ на этот вопрос мне вообще-то и не требовался. Я только спрашивал, а не указывал, кому, как и каких набирать сотрудников к себе на работу.

[Visual1]

Остапа понесло..... А эта тема вообще о чем?

Да трудно понять. Я предполагал, что на собеседовании у программиста проверяют умение программировать. Понимать опасности, которые иногда могут быть скрыты даже в несложном на первый взгляд коде. Я предложил задачу на эту тему, и несколько человек этой задачей заинтересовались, начали решать. Один человек дал правильное и подробное объяснение своего решения. Казалось бы, все на этом? Но г-ну dzid'у (который в решении не участвовал) вдруг это почему-то сильно не понравилось. Когда задача была уже решена, он почему-то стал реагировать неадекватно, очень бурно и эмоциально. Объявил подобные задачи "фимозом головного мозга", а также "задроченностью на мелкую специфику языка программирования". Не могу понять, как я мог своей несложной задачкой настолько сильно обидеть г-на dzid'a, что он стал выражаться настолько грубо и оскорбительно насчет моей задачи.

В общем, мне дали понять, что такие задачи программистам не нужны. Для программиста гораздо важнее уметь решать задачи по геометрии, про многоугольники. По крайней мере, такова точка зрения г-на dzid'a. Вот такой ответ на ваш вопрос.

[dzid]

пишите ТЗ. то, что вы наформулировали вполне нормально решается данными методами, которые, кстати, наглядны, просты и гарантируют верный результат.

Эээ. Разрешите увидеть доказательство такого сильного утверждения. Особенно насчет гарантируют

с многоугольниками операция нахождения центра производится во время его создания, и хранится в описании многоугольника, так что в рантайме поиск центра сводится к чтению свойства объекта.

А где код на SQL? И как это сделать, если

В плоскости есть выпуклый многоугольник, состоящий из произвольного числа точек, заданных своими координатами (x, y)

Что-то я тут свойств не помню... А идея с утолщениями линий все равно плоха.

Сообщение отредактировал dzid: 24.12.2009, 14:41:27

[dzid]

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

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

Если вы задаете в первую очередь вопрос о том, как управлять автобусом типа ЛАЗ-677 (так как именно их использует ваш автопарк) - вы поступаете глупо. Соискатель, ни разу в жизни не видевший ЛАЗ, но водивший ЛиАЗ, IKARUS, и еще много чего, на этот вопрос не ответит, сформировав у вас ложно-отрицательное впечатление о себе. На самом деле же это неважно и решается прохождением несколькодневных курсов.

Аналогию с вашим случаем увидите, я надеюсь.

[Visual1]

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

[yedyge]

Эээ. Разрешите увидеть доказательство такого сильного утверждения. Особенно насчет гарантируют

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

И как это сделать,

сказал же. второй раз пояснять вам бесперспективно.

[dzid]

Эээ. Разрешите увидеть доказательство такого сильного утверждения. Особенно насчет гарантируют

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

Ну как же. Знаний вам не хватает для таких вещей, так и скажите. Или за слова вы больше не отвечаете?

И как это сделать,

сказал же. второй раз пояснять вам бесперспективно.

Слив засчитан. БыдлокодерCode monkey detected.

Сообщение отредактировал dzid: 27.12.2009, 20:16:16

[v04bvs]

В общем, мне дали понять, что такие задачи программистам не нужны. Для программиста гораздо важнее уметь решать задачи по геометрии, про многоугольники. По крайней мере, такова точка зрения г-на dzid'a. Вот такой ответ на ваш вопрос.

Я считаю, что знание закоулков какого-либо ЯП большинству программистов менее полезно, чем знание предметной области (геометрия/финансы/юриспруденция/бухгалтерское дело). С другой стороны умение проектировать программы (паттерны, опыт) не менее важно.
При этом лично я в таких закоулках обычно разбираюсь, но это уже конкретно мои свойства. В реальной работе код, в котором быстро разберусь только я, я писать не буду.

[Visual1]

Я считаю, что знание закоулков какого-либо ЯП большинству программистов менее полезно, чем знание предметной области (геометрия/финансы/юриспруденция/бухгалтерское дело). С другой стороны умение проектировать программы (паттерны, опыт) не менее важно.
При этом лично я в таких закоулках обычно разбираюсь, но это уже конкретно мои свойства. В реальной работе код, в котором быстро разберусь только я, я писать не буду.

Все, что было в моем примере - это один простенький оператор return в блоке try, и за ним такой же простенький блок finally с единственной строчкой в нем. Называть такое "закоулками"? Как говорят в таких случаях, "я фигею, дорогая редакция".

Спорить с вами насчет "закоулков" (как вы изволили назвать мой несложный пример), я считаю, просто нет смысла. Да и Новый год уже скоро. С наступающим Новым годом, уважаемые дамы и господа!

[maratm]

Что вы тут не тем увлекаетесь
return он и в Африке return
Это скорее из раздела "помошь юнному программисту"