Растеризатор 2D-сцены

Нужно написать функцию render(scene), которая возвращает картинку как список строк пикселей (r, g, b). Пиксель закрашивается, если его центр лежит внутри фигуры. Фигуры бывают пяти видов: прямоугольник с полуоткрытыми границами, круг, эллипс, многоугольник с правилами заливки nonzero и evenodd и толстая линия. Цвет задаётся в форматах #rgb, #rgba, #rrggbb и #rrggbbaa, у фигуры может быть opacity, линейный градиент и аффинное преобразование. Цвета смешиваются по формуле floor(src*α + dst*(1-α) + 0.5).

Напиши на Python 3.12 растеризатор двумерной сцены: один модуль, только стандартная библиотека. Сторонние библиотеки (PIL, numpy и любые другие) использовать нельзя.

## Интерфейс

```python
def render(scene: dict) -> list[list[tuple[int, int, int]]]:
    ...
```

Функция возвращает картинку как список строк сверху вниз. Каждая строка это список пикселей слева направо, каждый пиксель это кортеж `(r, g, b)` из целых чисел от 0 до 255. Элемент `result[j][i]` соответствует пикселю в столбце `i` и строке `j`.

## Сцена

```python
{
  "width": 320, "height": 200,          # размер холста в пикселях
  "background": "#0b1d3a",              # цвет фона
  "shapes": [ {...}, {...} ]            # фигуры, рисуются по порядку, каждая следующая поверх предыдущих
}
```

## Координаты и пиксели

Ось x направлена вправо, ось y вниз. Пиксель `(i, j)` занимает квадрат от `i` до `i+1` по x и от `j` до `j+1` по y. Пиксель закрашивается фигурой, если **центр пикселя** `(i + 0.5, j + 0.5)` лежит внутри фигуры. Сглаживания нет.

## Цвета

Цвет задаётся строкой: `#rgb`, `#rgba`, `#rrggbb` или `#rrggbbaa`, шестнадцатеричные цифры в любом регистре. В коротких формах каждая цифра удваивается (`#a3f` означает `#aa33ff`). Если альфа не указана, она равна 255. У фона альфа игнорируется, фон всегда непрозрачный. Любая другая строка считается ошибкой.

## Фигуры

У каждой фигуры есть поле `type` и поле `fill` (цвет или градиент). Необязательные поля: `opacity` (число от 0 до 1, по умолчанию 1) и `transform` (см. ниже). Все координаты фигуры заданы в её локальной системе.

- `rect`: поля `x`, `y`, `w`, `h`. Точка внутри, если `x <= px < x + w` и `y <= py < y + h`. При `w <= 0` или `h <= 0` фигура пустая.
- `circle`: поля `cx`, `cy`, `r`. Точка внутри, если `(px - cx)² + (py - cy)² <= r²`.
- `ellipse`: поля `cx`, `cy`, `rx`, `ry`. Точка внутри, если `((px - cx) / rx)² + ((py - cy) / ry)² <= 1`. При `rx <= 0` или `ry <= 0` фигура пустая.
- `polygon`: поле `points` (список точек `[x, y]`, не меньше трёх, многоугольник замкнут) и необязательное `fill_rule`: `"nonzero"` (по умолчанию) или `"evenodd"`. Принадлежность точки определяется лучом из неё вправо. Ребро `(x0, y0) → (x1, y1)` пересекает луч, если `y0 <= py < y1` или `y1 <= py < y0`, и при этом `x0 + (py - y0) * (x1 - x0) / (y1 - y0) > px`. Каждое такое ребро добавляет к числу оборотов `+1`, если `y1 > y0`, иначе `-1`. Для `nonzero` точка внутри, если сумма не равна нулю, для `evenodd` точка внутри, если число пересекающих рёбер нечётное.
- `line`: поля `x1`, `y1`, `x2`, `y2`, `width`. Точка внутри, если расстояние от неё до отрезка не больше `width / 2`. Если концы совпадают, получается круг.

## Преобразование

`transform` задаётся шестью числами `[a, b, c, d, e, f]` и переводит локальную точку `(x, y)` в точку холста `(a*x + c*y + e, b*x + d*y + f)`. Чтобы проверить пиксель, его центр переводится обратным преобразованием в локальные координаты, и проверка идёт там. Поэтому круг под масштабом становится эллипсом, а толщина линии масштабируется вместе с ней. Если преобразование вырожденное (`a*d - b*c == 0`), фигура не рисуется. Без `transform` локальные координаты совпадают с координатами холста.

## Градиент

```python
{"type": "linear", "x1": 0, "y1": 0, "x2": 100, "y2": 0, "stops": [[0, "#000"], [0.5, "#f00"], [1, "#fff"]]}
```

Координаты градиента тоже локальные. Для точки `p` параметр `t` равен скалярному произведению `(p - p1)` на `(p2 - p1)`, делённому на `|p2 - p1|²`, и обрезается до отрезка `[0, 1]`. Если `p1` совпадает с `p2`, то `t = 0`. Точки остановки `stops` идут по возрастанию смещения. Если `t` не больше первого смещения, берётся первый цвет. Если не меньше последнего, берётся последний. Иначе берутся соседние остановки с `o_i <= t <= o_{i+1}`, и каждый канал, включая альфу, интерполируется линейно, без округления на этом шаге. Если две соседние остановки стоят в одной точке, берётся цвет второй. Пустой список `stops` считается ошибкой.

## Наложение цветов

Для закрашиваемого пикселя берётся цвет заливки `(r, g, b, a)` в этой точке. Непрозрачность равна `α = a / 255 * opacity`. Каждый канал холста заменяется на `floor(src * α + dst * (1 - α) + 0.5)`, где `dst` это текущее целое значение канала. Результат ограничивается отрезком от 0 до 255.

## Ошибки

Неверный цвет, неизвестный тип фигуры, многоугольник меньше чем из трёх точек и градиент без остановок должны вызывать `ValueError`.

## Производительность

Холст 800×600 с 400 небольшими фигурами и холст 640×480 с несколькими крупными полупрозрачными фигурами и градиентом должны рисоваться не дольше 4 секунд каждый на обычном ПК.

## Формат ответа

Ответь ТОЛЬКО кодом модуля в одном блоке ```python.

• 46 ручных сцен с ловушками. Среди них полуоткрытые границы прямоугольника и включительная граница круга, короткие записи цвета #abc и #f808, самопересекающаяся звезда с разными правилами заливки, вершины ровно на центрах пикселей, вырожденное преобразование, круг под масштабом, который становится эллипсом, толщина линии под масштабом, градиенты с обрезкой, со ступенькой и с совпадающими точками, а также смешивание цветов ровно на половине, где round() в Python даёт другой ответ.
• 150 случайных сцен из генератора с фиксированным seed, в каждой от 2 до 9 фигур с прозрачностью, градиентами и преобразованиями.
• 6 сцен, которые обязаны закончиться ошибкой ValueError: неверные цвета, неизвестный тип фигуры, многоугольник из двух точек, градиент без остановок.
• 2 замера скорости: 400 небольших фигур на холсте 800×600 и несколько крупных полупрозрачных фигур с градиентом на холсте 640×480. На каждый даётся 4 секунды, эталон укладывается в 0,5 и 0,8 секунды.
• Картинка сравнивается с эталоном попиксельно. Разница в 1 единицу по каналу допускается, потому что формулы можно записать по-разному. Сцена засчитывается, если не совпало не больше 0,1% пикселей, но не меньше трёх, это запас на центры пикселей ровно на границе фигуры.
• Сам стенд проверен эталоном: он проходит 202 сцены из 202 и оба замера скорости.

• Участвуют модели, которые дали рабочий код в первом тесте, плюс Grok 4.7. Каждая получила задание слово в слово, одним сообщением, без системного промпта и без инструментов, и не могла запустить свой код.
• Параметры рассуждения такие же, как в первом тесте: у Qwen включён enable_thinking, у GPT и Grok reasoning_effort: high, Opus через API получал thinking: adaptive и effort: max через нативный /v1/messages, Kimi и DeepSeek работали в режиме по умолчанию.
• Opus 5.5 дополнительно решал задачу агентом Claude Code с чистым контекстом. Ему разрешено одно чтение файла задания и одна запись решения, запускать код нельзя.
• В зачёт идёт код как есть. Вариант с правкой одной строки считается отдельно, только для понимания.
• Время считается от отправки запроса до последнего токена и зависит от загрузки серверов провайдера.

• Эталонный растеризатор написан по тексту задания, и стенд проверен им самим: 202 сцены из 202 и оба замера скорости за 0,45 и 0,83 секунды.
• При одинаковом числе сцен и замеров место определяет суммарное время двух замеров скорости.
• Первая попытка GPT-6.1 Sol оборвалась на шлюзе на 115-й секунде без ответа, засчитана вторая.
• Grok 4.7 через партнёрский шлюз не смог закончить ни одну задачу: его потоки обрывались посреди рассуждения, поэтому он в разделе исключённых.
• Время и токены Opus-агента оценочные, по объёму кэша контекста. Протокол агента проверен: одно чтение задания и одна запись решения.
• Opus-агент с effort: max добавлен 29.10.2026, после основного прогона, по тому же протоколу: одно чтение задания и одна запись решения, без запуска кода. Его запустили, чтобы сравнить с Opus через API на том же effort: max: через партнёрский шлюз модель рассуждает заметно меньше.

Эти прогоны не попали в рейтинг: результат определила не модель, а условия запуска. Ответы и код сохранены в папке.

• Grok 4.7 (0 из 202): Партнёрский шлюз каждый раз обрывал поток посреди рассуждения, и модель не успевала выдать ни строки кода. Это проблема доступа, а не модели. Grok стоит проверить через прямой API xAI. Две попытки оборвались на 652-й и 840-й секунде.