Инженерный тур. 2 этап

Приведенная функция для всех чисел от \(1\) до \(2^k\) принимает значение \(0\) ровно \(2^{k-2}\) раза. В частности, для всех чисел от \(1\) до \(2^{60}\) значение \(0\) будет получено \(2^{58} = 288230376151711744\) раза.

Опровергнем ряд утверждений примером, см. таблицу 1.1.

Неверные утверждения:

• В турнире выиграл или Богдан, или Глеб.
• В турнире победил мальчик.
• Первые три места заняли мальчики.

Этот пример также подтверждает следующие утверждения:

• Глеб мог занять второе место.
• Вера могла оказаться на первом месте.

Заметим, что хоть следующие ниже утверждения выполнены в примере, это не доказывает их истинность при любом другом исходе игр ввиду их формулировки:

• Последнее место заняла Ева.
• Богдан и Глеб сыграли между собой вничью.
• Глеб выиграл игру у Антона.

Рассмотрим их по отдельности:

• «Глеб выиграл игру у Антона»: это верное утверждение, потому что Антон не мог сыграть вничью, а Глеб не проиграл ни одной игры.
• «Богдан и Глеб сыграли между собой вничью»: это тоже верное утверждение, потому что Богдан и Глеб не проиграли ни одной игры, но они провели между собой игру на турнире — единственный исход в таком случае ничья.
• «Последнее место заняла Ева»: опровергнем это утверждение примером, см. таблицу 1.2.

Рассмотрим один из вариантов решения этой задачи.

Определим пустую очередь с приоритетом \(h\) — эта очередь будет работать с парами чисел, выполняя операции вставки и извлечения за \(\mathcal{O}(\log|h|)\).

Начнем итерироваться по массиву \(p\), начиная с первого элемента. Запомним, что в день \(i\) цена на напиток равна \(p_i\), и в этот день можно было купить \(k\) банок — выполним вставку в очередь \(h\) пары чисел \((p_i, k)\). Затем выполним операцию извлечения пары \((price, rem)\) (цена напитка в какой-то день и количество банок, которое можно было купить в этот день) из очереди \(h\) — ввиду природы очереди с приоритетом, \(price\) будет наименьшим из всех существующих \(price\) в очереди \(h\), прибавим к ответу \(price\), если при этом \(rem \geqslant 2\), то в тот же день, которому соответствует цена \(price\), можно было купить еще минимум одну банку — запомним это и выполним вставку в \(h\) пары \((price, rem-1)\).

Сложность: \(\mathcal{O}(n \cdot \log n)\).

Ниже представлено решение на языке Python.

import sys
from heapq import heappop, heappush

n, k = map(int, sys.stdin.readline().split())
p = list(map(int, sys.stdin.readline().split()))

res = 0
h = []

for i in range(n):
    heappush(h, (p[i], k))

    price, rem = heappop(h)
    res += price)

    if rem > 1:
        heappush(h, (price, rem - 1))

print(res)

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

Предположим, \(h_i \leqslant w_i\), если это не так, то поменяем числа в каждой такой паре, чтобы ширина каждого прямоугольника была не меньше, чем высота. После этого отсортируем все прямоугольники в первую очередь по невозрастанию ширины, а затем — по невозрастанию высоты.

Выберем первый прямоугольник, который имеет наибольшую ширину. Если таких прямоугольников несколько, то выберем самый высокий из них. Пусть ширина этого прямоугольника равна \(w'\), а высота — \(h'\). Запомним эти значения.

Затем мы будем последовательно рассматривать остальные прямоугольники в порядке их сортировки. Если текущий прямоугольник имеет ширину \(w\) и высоту \(h\) (\(w \geqslant h\)), а \(h \leqslant h''\), то это означает, что текущий прямоугольник полностью помещается внутри уже существующей фигуры и не увеличивает ее площадь. Поэтому такие прямоугольники пропустим.

Более интересен случай, когда \(h > h'\), в такой ситуации прибавим к ответу площадь прямоугольника, ограниченного по оси \(X\) с \(w\) по \(w'\) и по оси \(Y\) с \(0\) по \(h'\).

Заменим \(w'\) на \(w\), то есть присвоим переменной \(w'\) значение \(w\). Аналогично присвоим переменной \(h'\) значение \(h\). Продолжая этот процесс для оставшихся прямоугольников, можно вычислить площадь всей фигуры за исключением последнего прямоугольника, который совпадает с самым высоким.

В конце прибавим к ответу \(w' \cdot h'\) — это площадь «неучтенного» прямоугольника.

Сложность: \(\mathcal{O}(n \cdot \log n)\).

Ниже представлено решение на языке Python.

import sys

n = int(sys.stdin.readline())

d = []
for i in range(n):
    w, h = map(int, sys.stdin.readline().split())
    if w >= h:
        w, h = h, w
    d.append([w, h])

d.sort(key=lambda x: (-x[0], -x[1]))

res = 0
a, b = d[0]

for w, h in d[1:]:
    if h > b:
        res += b * (a - w)
        b = h
        a = w
        
res += a * b

print(res)

Нужно уметь быстро прибавлять на отрезке. Идея, которая напрашивается сразу — дерево отрезков (ДО), однако в стандартном виде это будет работать слишком медленно.

Во-первых, координаты находятся в диапазоне от \(-10^9\) до \(10^9\), что не позволит задать координаты и использовать в дереве явно. Применим сжатие координат — рассмотрим все координаты, которые встречаются в задаче, отсортируем их и переназначим значения: так, самой малой координате будет соответствовать 1, второй по величине будет соответствовать 2 и так далее. Итого имеем не более \(2n\) различных координат.

Во-вторых, пусть даже с \(2n\) различными координатами, ДО в привычном виде все еще не справится с задачей, так как блок в общем случае занимает не одну координату, а отрезок, то есть нужно обновлять значения в ДО для каждой точки в отрезке, а это не пройдет по времени и ничем не лучше реализации без ДО.

Применим оптимизацию, позволяющую прибавлять \(+1\) в ДО не в одной точке, а на отрезке. Эта оптимизация использует идею «ленивых вычислений» или «отложенных» (https://ru.algorithmica.org/cs/segment-tree/lazy-propagation/, pdf-версия веб-страницы: https://disk.yandex.ru/i/Nj8_d-2lzCfb9w), а именно: когда текущая вершина в ДО покрывает целиком часть отрезка, на котором выполняется прибавление, то значение в этой вершине увеличивается, а далее не спускаемся в дочерние вершины. Такая операция сопряжена с рядом возможных случаев: если в текущей вершине уже было записано обновление ранее — то спускаем его в дочерние вершины, а только после записываем в текущую вершину новое значение. Вообще, всегда оказавшись в какой-то вершине, спускаем обновления вниз по дереву.

Ответ на задачу — максимальное число в вершине дерева.

Всего тратим время на сортировку координат \(n \cdot \log n\).

Затем \(n\) раз выполняем операции на дереве. Каждая операция затрагивает \(4 \cdot \log n\) вершин дерева.

Сложность: \(\mathcal{O}(n \cdot \log n)\).

Ниже представлено решение на языке Python.

import sys


class SegmentTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (4 * size)
        self.lazy = [None] * (4 * size)

    def _apply(self, node, start, end, value):
        self.tree[node] = value
        if start != end:
            self.lazy[node * 2] = value
            self.lazy[node * 2 + 1] = value
        self.lazy[node] = None

    def _update_range(self, node, start, end, l, r, value):
        if self.lazy[node] is not None:
            self._apply(node, start, end, self.lazy[node])

        if start > end or start > r or end < l:
            return

        if start >= l and end <= r:
            self._apply(node, start, end, value)
            return

        mid = (start + end) // 2
        self._update_range(node * 2, start, mid, l, r, value)
        self._update_range(node * 2 + 1, mid + 1, end, l, r, value)
        self.tree[node] = max(self.tree[node * 2], self.tree[node * 2 + 1])

    def update_range(self, l, r, value):
        self._update_range(1, 0, self.size - 1, l, r, value)

    def _query_range(self, node, start, end, l, r):
        if start > end or start > r or end < l:
            return -float('inf')

        if self.lazy[node] is not None:
            self._apply(node, start, end, self.lazy[node])

        if start >= l and end <= r:
            return self.tree[node]

        mid = (start + end) // 2
        left_query = self._query_range(node * 2, start, mid, l, r)
        right_query = self._query_range(node * 2 + 1, mid + 1, end, l, r)
        return max(left_query, right_query)

    def query_range(self, l, r):
        return self._query_range(1, 0, self.size - 1, l, r)


def solve():
    w = int(sys.stdin.readline())
    n = int(sys.stdin.readline())

    lr = []
    uniq = {0, w - 1}

    for i in range(n):
        l, r = map(int, sys.stdin.readline().split())
        lr.append([l, r])
        uniq.add(l)
        uniq.add(r - 1)

    sorted_uniq = sorted(list(uniq))
    new_x = {sorted_uniq[i]: i for i in range(len(sorted_uniq))}

    seg_tree = SegmentTree(len(uniq))
    seg_tree.update_range(l=sorted_uniq.index(0),
                          r=sorted_uniq.index(w - 1),
                          value=1)

    for l, r in lr:
        nl, nr = new_x[l], new_x[r - 1]
        mx = seg_tree.query_range(nl, nr)
        if mx >= 1:
            seg_tree.update_range(nl, nr, mx + 1)

    max_height = seg_tree.query_range(0, len(uniq))
    print(max_height)
    return max_height


if __name__ == '__main__':
    solve()

Напряжение конденсатора после закрытия первого ключа: \[U_{Co} = E \cdot \left(1 - \frac{1}{k_1}\right).\]

Полная энергия колебательной системы: \[W = \frac{C \cdot U_{Co}^2}{2}.\]

Энергия, запасенная в конденсаторе в момент разрыва предохранителя: \[W_C = W - \frac{L \cdot I^2}{2}.\]

Заряд на конденсаторе: \[q = \sqrt{2 \cdot W_C \cdot C}.\]

Ниже представлено решение на языке C++.

#include <stdio.h>
#include <cmath>
int main() {
    float R, k, I, E, C, L, U, W, Wc, q;
    scanf("%f", &R);
    scanf("%f", &k);
    scanf("%f", &I);
    scanf("%f", &E);
    scanf("%f", &C);
    scanf("%f", &L);
    U=E*(1-1/k);
    W=C*U*U/2;
    Wc=W-L*I*I/2;
    q=sqrt(Wc*C*2);
    printf("%.6f", q);
    return 0;
}

Для начала необходимо пересчитать матрицу высот в матрицу энергетических затрат по формуле: \[Q_{\text{кип}} = C \cdot m \cdot \Delta t,\] где:

• \(Q_{\text{кип}}\) — количество энергии на кипячение воды в чайнике, Дж;
• \(C\) — удельная теплоемкость воды, Дж/(кг\(\cdot°\)C);
• \(\Delta t\) — разница между температурой кипения воды на данной высоте и начальной температурой воды, °C.

Для определения \(\Delta t\) воспользуемся следующей формулой: \[\Delta t = \frac{1000 - h}{30} + 80,\] где \(h\) — высота горы, м.

Также необходимо знать количество запасенной энергии в аккумуляторе в джоулях (Дж): \[Q_{\text{ак}} = Q \cdot 3{,}6 \cdot V,\] где \(Q\) — емкость аккумулятора, мАч, \(V\) — напряжение аккумулятора, В.

Решение заключается в переборе возможных вариантов прохождения. Приведенное ниже решение представляет собой рекурсивный проход с оценкой пути. В зависимости от положения любителя чая на поле (в матрице) \(3\times 3\) клетки необходимо учитывать возможность его движения. Оценка пути заключается в вычислении количества выпитых чашек чая.

Ниже представлено решение на языке Python.

n = int(input())
h = [(1000 - x) / 30 + 80 for _ in range(3) for x in map(int, input().split())]
q = int(input())

C_water = 4200
m_water = 0.4
V = 12
Q = q * 3.6 * V

q_for_cup = [C_water * m_water * h[i] for i in range(9)]


def walking(n, tea_drink, energy_remain, used):
    best = tea_drink + int(energy_remain / q_for_cup[n])

    if q_for_cup[n] > energy_remain:
        return best

    for dn in [1, -1, 3, -3]:
        if not 0 <= n + dn <= 8:
            continue
        if abs(dn) != 3 and not 0 <= n % 3 + dn <= 2:
            continue
        if (1 << n + dn) & (used) != 0:
            continue
        best = max(best, walking(n + dn, tea_drink + 1, energy_remain - q_for_cup[n], used | (1 << n + dn)))

    return best


print(walking(n, 0, Q, 1 << n))

Для решения данной задачи необходимо было воспользоваться предложенной статьей и таблицей зависимости плотности насыщенного пара от температуры. Из статьи про психрометр надо было подметить два момента:

1. начение психрометрического коэффициента равно 0,0011 (по условию в оранжерее естественная вентиляция без сквозняков);
2. формула для расчета значения влажности: \[\varphi = 100 \left( \frac{d_w}{d_s} - \alpha \cdot B \frac{t - t_w}{d_s} \right).\]

В этой формуле уже известны две температуры (\(t\) и \(t_w\)), атмосферное давление, а также психрометрический коэффициент. Остается найти плотность насыщенного пара. Для этого была предоставлена таблица соответствия плотности насыщенного пара от температуры, но в качестве входных данных может выступать любое вещественное число от \(-30\) до \(30\).

Первое, что приходит в голову — округлять температуру до ближайшего целого четного, но точнее будет использовать кусочно-линейную функцию. Такой подход активно используется для преобразования аналоговых сигналов с помощью микроконтроллеров. Суть в том, что, зная приращение по температуре и по плотности, можно найти наклон линейной функции для участка температур в 2°. Из таких небольших участков составляется кусочно-линейная функция, стремящаяся к нелинейной функции изменения плотности насыщенного пара. Значения плотностей насыщенного пара, а также наклоны линейных функций заносятся в соответствующие массивы. На основе известной температуры рассчитывается, к какой линейной функции принадлежит необходимая плотность насыщенного пара, и через линейную функцию находится ее приближенное значение. Все известные величины подставляются в формулу, и вычисляется относительная влажность воздуха. При выводе значение округляется до целых.

Ниже представлено решение на языке C.

#include <stdio.h>
#include <stdint.h>
#include <math.h>

#define ALPHA            0.0011
#define DEFAULT_PREASURE     760
#define VALID_INDEX(index, max) ((index > max) ? max : index)

float density_table[] = {0.28, 0.35, 0.43, 0.52, 0.64, 0.77, 0.94, 1.13, 1.36, 1.63, 2.14, 2.54, 
2.99, 3.51, 4.13, 4.84, 5.6, 6.4, 7.3, 8.3, 9.4, 10.4, 12.1, 13.6, 15.4, 17.3, 19.4, 21.8, 24.4, 
27.2};

float k_table[] = {0.035, 0.04, 0.045, 0.06, 0.065, 0.085, 0.095, 0.115, 0.135, 0.255, 0.2, 
0.225, 0.26, 0.31, 0.355, 0.38, 0.4, 0.45, 0.5, 0.55, 0.5, 0.85, 0.75, 0.9, 0.95, 1.05, 1.2, 1.3, 
1.4, 1.55};

int main(){
float t1, t1w;
float P1 = DEFAULT_PREASURE;
scanf("%f%f%f", &t1, &t1w, &P1);
uint8_t i1, i1w;
i1 = VALID_INDEX((uint8_t)(t1 + 30) / 2, 29);
i1w = VALID_INDEX((uint8_t)(t1w + 30) / 2, 29);
float d1, d1w;
d1 = k_table[i1] * (t1 - (-30 + 2 * i1)) + density_table[i1];
d1w = k_table[i1w] * (t1w - (-30 + 2 * i1w)) + density_table[i1w];
float phi = 100.0f * (d1w - 0.0011 * P1 * (t1 - t1w)) / d1;
printf("%.0f%%\n", phi);
return 0;
}

Для решения данной задачи необходимо понять, каким образом ускорение, измеряемое акселерометром, преобразуется в напряжение на входе. Для этого обратимся к документации на акселерометр, которая была приложена к заданию. Акселерометр рассчитан на ускорение до 3g. Смещение нуля, согласно документации, составляет 1,65 В, при питании в 3,3 В. Приращение напряжения от изменения ускорения по оси 300 мВ/g. Отсюда выведем формулу расчета: \[a = \frac{\left(\frac{adc \cdot 5}{1023} - 1{,}65\right)}{0{,}300} \cdot 9{,}8 = \frac{\left(\frac{adc \cdot 5000}{1023} - 1650\right)}{300} \cdot 9{,}8 = \left(\frac{adc \cdot 50}{3069} - 5\right) \cdot 9{,}8.\] Для каждого показания АЦП по трем осям рассчитывается ускорение в метрах секунду за секунду. Далее применим формулу из application note для расчета крена и тангажа. Эти формулы справедливы для большинства акселерометров и легко находятся в статьях: \[roll = \operatorname{arctg} \left( \frac{a_y}{a_z} \right);\] \[pitch = \operatorname{arctg} \left( \frac{-a_x}{\sqrt{a_y^2+a_z^2}} \right).\]

Подставляя в эти формулы рассчитанные ранее ускорения, вычисляются углы крен и тангаж в радианах, остается только пересчитать радианы в градусы.

Ниже представлено решение на языке C++.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define PI 3.1415926535
#define PI_2 (PI / 2.0)
#define PI_4 (PI / 4.0)

#define ABS(x) ((x < 0) ? -x : x)
#define SQR(x) (x * x)
#define CONV(x) ((x - 1) / (x + 1))
#define DEGREES(x) ((float)x * 180.0f / PI)
#define ATAN(x) (x * (0.9992150 + SQR(x) * (-0.3211819 + SQR(x) * (0.1462766 + SQR(x) * (-0.0389929)))))

float fast_rsqrt(float number){ 
    const float x2 = number * 0.5F;
    const float threehalfs = 1.5F;

    union {
        float f;
        uint32_t i;
    } conv = {number};
    conv.i = 0x5f3759df - ( conv.i >> 1 );
    conv.f *= threehalfs - x2 * conv.f * conv.f;
    return conv.f;
}
float fast_atan(float number){
    if (number > 0)
        return PI_4 + ATAN(CONV(number));
    else
        return -(PI_4 + ATAN(CONV(-number)));
}
int main(){
    uint32_t N;
    scanf("%u", &N);
    uint32_t* array = (uint32_t*)calloc(N * 3, sizeof(uint32_t));
    for (uint32_t i = 0; i < N * 3; i += 3)
        scanf("%u %u %u", &array[i], &array[i + 1], &array[i + 2]);
    for (uint32_t i = 0; i < N * 3; i += 3){
        float ax_x = ((float)array[i] * 50 / 3069 - 5) * 9.8;
        float ax_y = ((float)array[i + 1] * 50 / 3069 - 5) * 9.8;
        float ax_z = ((float)array[i + 2] * 50 / 3069 - 5) * 9.8;
        float roll = fast_atan(ax_y / -ax_z);
        float pitch = fast_atan(-ax_x * fast_rsqrt(SQR(ax_y) + SQR(ax_z)));
        printf("%.2f %.2f %.2f %.0f %.0f\n", ax_x, ax_y, ax_z, DEGREES(roll), DEGREES(pitch));
    }
    free(array);
    return 0;
}

Все тестовые задания созданы на основе официальных заданий из теоретических билетов ГИБДД на право управления транспортным средством категории B. В частности, были использованы задания на нерегулируемые перекрестки. Соответственно, все правила, определяющие порядок проезда, указаны в ПДД на момент 2024 года.

Основная идея решения в следующем: на перекрестке возможны восемь направлений. Для каждого направления условно можно выделить две полосы: въезд и выезд. Так как на территории Российской Федерации движение правостороннее, то въезд всегда будет «правее» или «дальше по часовой стрелке», чем выезд.

Таким образом, можно представить все возможные направления в виде окружности, на которой с равным шагом расположены 16 точек. Каждая из точек обозначает въезд или выезд для каждого направления. Каждый из автомобилей стремится отправиться из начальной точки в конечную. Начальную и конечную точку можно соединить линией и получить отрезок или вектор.

Примем изначально приоритет каждого автомобиля равным 1 (должен проехать первым). Далее необходимо проверить, пересекаются ли отрезки/вектора автомобилей. Если они не пересекаются, значит, автомобили на перекрестке могут разъехаться, не пересекая траекторию друг друга (в реальности, конечно, может существовать перекресток, где такое окажется невозможным, но команда разработчиков провела наблюдение за несколько перекрестками и решила, что такое допущение работает в подавляющем большинстве случаев). Автомобили, чьи траектории не пересекаются, могут оставить равный приоритет между собой.

В случае, если траектории все-таки пересеклись, необходимо определить, чей приоритет останется более высоким. В ПДД это определяется «помехой справа». Простыми словами помехой справа является такая помеха, которая в моменте находится справа от водителя. Если водитель 1 едет прямо в одном направлении, а перпендикулярно ему едет водитель 2 с правой стороны, водитель 1 должен уступить дорогу, т. к. водитель 2 является для него помехой справа.

С точки зрения программирования для определения помехи справа можно использовать разные способы. Самым простым, с точки зрения реализации, является расчет векторного произведения двух векторов движения. Если векторное произведение положительное, то помехой справа является один автомобиль, если отрицательное, то другой. Здесь может возникнуть сложная ситуация при расчете, если конечная точка у обоих автомобилей одинаковая. Для устранения этой проблемы каждый вектор/отрезок можно немного продлить.

Таким образом стоит проверить каждую пару автомобилей. Во избежание неточностей при решении рекомендуем сделать проверку итерационной. Так, в каждой итерации приоритет автомобиля может увеличиться только на 1. Всего итерационным образом нужно провести проверки 3 раза, что по условию задачи будет достаточным (максимум 4 автомобиля, максимальный приоритет может быть 4).

С точки зрения распределения приоритета, с учетом существования главной дороги, логика значительно не меняется, за исключением того факта, что оба автомобиля с главной дороги распределяют приоритет между собой согласно правилам, описанным выше; автомобиль с главной дороги имеет приоритет относительно автомобиля со второстепенной дороги безусловно; автомобили со второстепенной дороги распределяют приоритет согласно правилам, описанным выше. Далее остается только сформировать посылку по правилам, приведенным в задании.

В коде ниже есть закомментированные строки, выводящие промежуточные результаты. Это позволяет лучше понять логику кода.

Ниже представлено решение на языке Python.

import json
import math

def polar_to_cartesian(radius, angle_deg):
    """Преобразует полярные координаты в декартовые."""
    angle_rad = math.radians(angle_deg)
    x = radius * math.cos(angle_rad)
    y = radius * math.sin(angle_rad)
    return x, y

def is_intersecting_and_right(line1, line2):
    """
    Проверяет, пересекаются ли траектории, включая проверку "помеха справа"
    для продленных линий в случае совпадения конечных точек.
    """
    def determinant(a, b, c, d):
        return a * d - b * c

    def vector_cross_product(ax, ay, bx, by):
        """Векторное произведение для определения относительного положения точки."""
        return ax * by - ay * bx

    def are_points_equal(p1, p2, epsilon=1e-6):
        """Сравнивает два пункта с учетом допустимой погрешности."""
        return abs(p1[0] - p2[0]) < epsilon and abs(p1[1] - p2[1]) < epsilon

    def extend_point(p1, p2, factor=1.0):
        """Продлевает точку p2 на основе направления от p1 к p2."""
        dx = p2[0] - p1[0]
        dy = p2[1] - p1[1]
        return (p2[0] + dx * factor, p2[1] + dy * factor)

    x1, y1, x2, y2 = *line1[0], *line1[1]
    x3, y3, x4, y4 = *line2[0], *line2[1]

    # Проверяем совпадение конечных точек
    if are_points_equal((x2, y2), (x4, y4)):
        '''print("Конечные точки совпадают. Проверяем продленные линии.")'''
        # Продление линий
        extended1 = extend_point((x1, y1), (x2, y2), factor=0.1)
        extended2 = extend_point((x3, y3), (x4, y4), factor=0.1)
        '''print(f"Продленная точка для линии 1: {extended1}")
        print(f"Продленная точка для линии 2: {extended2}")'''

        # Проверяем пересечение для продленных линий
        vec1_x, vec1_y = extended1[0] - x1, extended1[1] - y1
        vec2_x, vec2_y = extended2[0] - x3, extended2[1] - y3
        cross = vector_cross_product(vec1_x, vec1_y, vec2_x, vec2_y)
        return True, cross < 0

    # Проверяем пересечение обычным образом
    det = determinant(x2 - x1, x3 - x4, y2 - y1, y3 - y4)
    if det == 0:
        return False, False

    t = determinant(x3 - x1, x3 - x4, y3 - y1, y3 - y4) / det
    u = determinant(x2 - x1, x3 - x1, y2 - y1, y3 - y1) / det

    if 0 <= t <= 1 and 0 <= u <= 1:
        vec1_x, vec1_y = x2 - x1, y2 - y1
        vec2_x, vec2_y = x4 - x3, y4 - y3
        cross = vector_cross_product(vec1_x, vec1_y, vec2_x, vec2_y)
        return True, cross < 0

    return False, False

def process_intersection(data, iterations=3):
    radius = 1
    step_angle = 22.5
    
    # Определение точек и превосходства
    lanes_map = {
        "north": 0, "north-east": 2, "east": 4, 
        "south-east": 6, "south": 8, "south-west": 10,
        "west": 12, "north-west": 14
    }
    directions_map = {
        "north": 1, "north-east": 3, "east": 5, 
        "south-east": 7, "south": 9, "south-west": 11,
        "west": 13, "north-west": 15
    }
    superior_points = {lanes_map[lane] for lane in data["intersection"]["priority_lanes"]}
    '''print(f"Точки превосходства: {superior_points}")'''
    
    # Формирование траекторий
    vehicles = data["vehicles"]
    trajectories = []
    for vehicle in vehicles:
        start_idx = lanes_map[vehicle["lane"]]
        end_idx = directions_map[vehicle["direction"]]
        start_point = polar_to_cartesian(radius, start_idx * step_angle)
        end_point = polar_to_cartesian(radius, end_idx * step_angle)
        trajectories.append((start_point, end_point, start_idx))
        '''print(f"Траектория автомобиля {vehicle['vehicle_id']}: стартовая точка {start_idx}, конечная точка {end_idx}")'''

    # Итеративный процесс перераспределения приоритетов
    priorities = [1] * data["intersection"]["vehicle_count"]
    for iteration in range(iterations):
        '''print(f"\nИтерация {iteration + 1}")'''
        new_priorities = priorities[:]
        for i in range(len(trajectories)):
            for j in range(i + 1, len(trajectories)):
                start_idx_i = trajectories[i][2]
                start_idx_j = trajectories[j][2]
                
                # Проверяем "превосходство" только если траектории пересекаются
                intersects, is_right = is_intersecting_and_right(
                    (trajectories[i][0], trajectories[i][1]),
                    (trajectories[j][0], trajectories[j][1])
                )
                
                if intersects:
                    if new_priorities[i] == new_priorities[j]:  # Меняем приоритет только если они равны
                        if (start_idx_i in superior_points) != (start_idx_j in superior_points):
                            if start_idx_i not in superior_points:
                                if new_priorities[i] <= iteration + 2:
                                    new_priorities[i] += 1
                                    '''print(f"Траектория {j + 1} имеет превосходство над траекторией {i + 1}. Приоритет траектории {i + 1} увеличен до {new_priorities[i]}.")'''
                            elif start_idx_j not in superior_points:
                                if new_priorities[j] <= iteration + 2:
                                    new_priorities[j] += 1
                                    '''print(f"Траектория {i + 1} имеет превосходство над траекторией {j + 1}. Приоритет траектории {j + 1} увеличен до {new_priorities[j]}.")'''
                        else:
                            if is_right:
                                if new_priorities[i] <= iteration + 2:
                                    new_priorities[i] += 1
                                    '''print(f"Автомобиль {vehicles[j]['vehicle_id']} помеха справа для автомобиля {vehicles[i]['vehicle_id']}. Приоритет {vehicles[i]['vehicle_id']} увеличен до {new_priorities[i]}.")'''
                            else:
                                if new_priorities[j] <= iteration + 2:
                                    new_priorities[j] += 1
                                    '''print(f"Автомобиль {vehicles[i]['vehicle_id']} помеха справа для автомобиля {vehicles[j]['vehicle_id']}. Приоритет {vehicles[j]['vehicle_id']} увеличен до {new_priorities[j]}.")'''
        priorities = new_priorities[:]
    
    # Формирование результата
    result = {"order": []}
    for i, vehicle in enumerate(vehicles):
        result["order"].append({
            "vehicle_id": vehicle["vehicle_id"],
            "priority": priorities[i]
        })
    
    '''print(f"\nИтоговые приоритеты: {result['order']}")'''
    return result

# Пример входных данных
with open("input.txt", encoding="UTF-8") as file_in:
    input_data = json.load(file_in)

# Вывод результата
output = process_intersection(input_data)
print(json.dumps(output, indent=2))