Аз паки засевши за еллинский в клеть, зане завтрие тест, а у мене не готовлено.

[nikaan]

"Le poète jouit de cet incomparable privilège, qu'il peut à sa guise être lui-même et autrui."
Прочитавши текст про говоры http://www.gramota.ru/book/village/map24.html
Вот обучуся и буду тако глаголати. Надо выну выходить за литературный нормы, пущай мат запрещают, мы этих ехидн и алекторов в http://bash.im ввергнем. Бяху говорили так предки, зане

Comments

[dimpas]

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

Написать на Sage код, генерирующий "интересные" прямые, и формулировать как set cover Integer Linear Programming problem, там же, в Sage, есть солверы для
таких задач.

[nikaan]

спасибо, я попробую. Но мне надо искать не множество, покрывающее всё, а множество, покрывающее всё ровно без одной точки (какой-нибудь).

[nikaan]

ну грубо говоря задача такая - для маленьких m (3,4,5) описать минимальные множества A_i, которые можно покрыть без одной точки m линиями, но нельзя m-1.

Минимальные A_i это значит нет множества с таким же свойством и выпуклой оболочкой внутри выпуклой оболочки A_i.

Ну и проверить правда ли, что минимальное такое m для треугольника (0,0)(k,-2k)(2k,-k) со всеми внутренними точками это в точности 2k.

Кажется, чтобы покрыть весь треугольник, надо не меньше 2k линий - но это неверно для k=2. А дальше не знаю.

[dimpas]

то есть одна точка всегда остается непокрытой?
т.е., например, для m=1 ответом будут тройки точек, с выпуклой облочкой без целых точек внутри?
A для m=2 уже не вполне очевидно?