Форум Всеукраїнської інтернет-олімпіади NetOI

Думаешь, он о твоих мозгах заботится? Что-то я сомневаюсь... По-моему, тут причина в другом...

Можно попробовать найти две крайние точки по оси абсцисс, затем Брезенхема одновременно по "длинной" линии и 2 "коротким", вычитая координаты Y следующих точек друг из друга (если они не совпадают) и еще 1 можно получить, сколько вертикально расположенных клеток находится между n и n+1. Суммируя их все можно получить искомое число.

Я мог бы указать вам на ошибки.
Я мог бы растрепать об этом всем.
Однако вижу - как талант вы хлипки.
А значит напишу: "КГ/АМ"!

Шучу, шучу... Просто вот о чем я подумал: сложность алгоритма то О(граница треугольника)
А дело вот в чем: за такую сложность можно и полегче решить.

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

В умові не сказано, якими є координати вершин трикутника.

Якщо вони гарантовано цілі, то це задача "Велика Трикутна Область" УОІ-2003, є розв'язок за O(log(m+n)), пояснення можна подивитися на www.uoi.kiev.ua (зайти на сторінку Всеукра 2003 р., там внизу лінк на архів олімпіади).

Якщо не обов'язково цілі, то я не знаю розв'язку, кращого за theta(min(m,n)) (але це _не_ гарантує, що такого розв'язку нема взагалі.). Така задача описана у багатьох місцях, і, зокрема, у моїй книжечці, що вийшла минулого літа у "Шкільному світі".

Коротко суть розв'язку за theta(min(m,n)):
0) якщо трикутник "низенький і широкий", повертаємо його на 90 градусів (або транспонуємо)
1)
for усіх ("стовпчиків" від x_i до (x_i)+1) do begin
  знаходимо точки перетину сторін трикутника з цими (x_i та (x_i)+1) верт. прямими, заокруглюємо нижні y-координати вгору й беремо максимум з двох, верхні y-координати вниз і беремо мінімум з двох, рахуємо зрізану різницю між ними (де "зрізана різниця" означає: якщо різниця менша нуля, вважаємо її нулем).
end
Сума усіх таких "зрізаних різниць" і є відповіддю.

Товарищи! Эта задача в той формулировке, в которой она дана, СЛОЖНЕЕ БТО!!!
В БТО давался ПРЯМОУГОЛЬНЫЙ треугольник, а у на произвольный. Поэтому нужно вписать треугольник в квадрат и вычитать три прямоугольных треугольника. Но тут есть один прикол. В БТО находилось число клеток ВНУТРИ треугольника, поэтому если мы вычтем из квадрата эти три треугольника, то получим кол-во квадратиков ВНУТРИ И НА ГРАНИЦЕ начального. Нам нужно еще вычесть и число клеток на границе. Тут можно усовершенствовать БТО, но есть одна проблема - иногда мы будем вычитать клеточки границы дважды. Особенно это чувствуется на узких треугольниках. Попробуйте, например, для треугольникв (0,0),(3,5),(5,3). В нем у самого острого угла две клеточки вычитаются дважды!!! Поэтому БТО тут не проходит

По условию написано, что нужно считать все клетки, которые лежат ПОЛНОСТЬЮ в пределах треугольника. Поэтому просто квадрат минус 3 БТО тут не катят! (с границей тут реальная сложность)

В принципе, можно поиздеваться с площадью треугольника, а так же кол-вом клеток, которые покрывают стороны треугольника. Тогда время работы O(1)!

Відредаговано Батыев Андрей (2005-12-01 18:08:08)

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

Задания 2 тура появились.
Ссылка тоже