Wataru

Многоугольник — это набор вершин, заданный в определенном порядке. Вот и определите нормали исходя из этого порядка. Например, задайте себе как стандарт обход многоугольника всегда по часовой стрелке, тогда нормаль грани всегда будет под 90 градусов влево от вектора, проведенного из вершины n в вершину n+1.
В 2д движках обычно так и делают.

Или

Одно из решений. Пусть сектор A описывается упорядоченной парой {A1,A2}, т.е. сектором считается область получающаяся при обходе окружности по часовой стрелке от точки А1 до точки А2.
1. Привести значения всех углов к диапазону от [0, 2pi).
2. Если A1 > A2, то разобъём сектор на два: S1 = [A1, 2pi) U [0, A2].
3. С помощью алгебры множеств и алгоритма пересечения обычных отрезков можно найти пересечение:
[A1, A2] ∩ [B1, B2] - обычный алгоритм
( [A1, 2pi) U [0, A2] ) ∩ [B1, B2] = ( [B1, B2] ∩ [A1, 2pi) ) U ( [B1, B2] ∩ [0, A2] ) - для каждого из пересечений обычный алгоритм
( [A1, 2pi) U [0, A2] ) ∩ ( [B1, 2pi) U [0, B2] ) - очевидно, что пересекаются как минимум в точке 0

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

Числа P и Q высчитываем с точностью до остатка от деления на Z := 10⁹+ 7.

Авторы обещают, что Q mod Z ≠ 0. Z — простое. Тогда НОД(Q mod Z, Z) = 1. Так называемый расширенный алгоритм Евклида (гуглите!) позволяет подобрать такие числа, чтобы m(Q mod Z) + nZ = 1.

Ваша задача — вывести ((P mod Z) · m) mod Z. Специально указал дважды mod Z: первое у вас будет при работе с числом P, второе — при генерации вывода.

Почему так? Возьмём вместо здоровенного Z цифру поменьше, 17. Если у вас получился результат 100/400, при расчётах выйдет цифра 15/9, и 9·2+17·(−1) = 1, и ваша задача — вывести (15·2) mod 17 = 13.

Если же у вас получилось, например, 35/140, при расчётах получается 1/4, 1·(−4)+17·1 = 1, и вы должны вывести (1·(−4)) mod 17 = 13. То есть: независимо от того, насколько сократимая дробь у вас получилась, вы получите один и тот же результат. Тут надо уточнить: там, где возможен отрицательный числитель, нужен не обычный % из Си++, а (a % Z; если получилось отрицательное — добавь Z).

Ну а арифметических переполнений просто не допускайте, Z = 10⁹ + 7 позволяет умножать в типе long long и не уходить в переполнение.

UPD. То, что Z — простое, даёт несколько выгод. Часто результат бывает круглый, и простота требует честно считать остаток, а не угадывать. Ну и побочек меньше.

Как можно реализовать, поворот динамического массива (матрица), без доп памяти?

Как-то так:

#include <stddef.h>
#include <stdio.h>

typedef int T;

void rotate(T *p, size_t m, size_t n, size_t (*turn)(size_t m, size_t n, size_t idx))
{
        size_t i, j, k;

        for (i = 0; i < m * n; ++i) {
                T tmp0, tmp1;

                for (j = 0; j < i; ++j) {
                        for (k = turn(m, n, j); k != i && k != j; k = turn(m, n, k)) {
                        }
                        if (k == i)
                                break;
                }
                if (j < i)
                        continue;

                tmp0 = p[i];
                for (j = turn(m, n, i); ; j = turn(m, n, j)) {
                        tmp1 = p[j];
                        p[j] = tmp0;
                        tmp0 = tmp1;
                        if (j == i)
                                break;
                }
        }
}

void dump(size_t m, size_t n, T p[m][n])
{
        size_t i, j;

        for (i = 0; i < m; ++i)
                for (j = 0; j < n; ++j)
                        printf("%d%s", p[i][j], j == n - 1 ? "\n" : ", ");
}

size_t turn_ccw(size_t m, size_t n, size_t idx)
{
        return (n - 1 - idx % n) * m + (idx / n);
}

size_t turn_cw(size_t m, size_t n, size_t idx)
{
        return (idx % n) * m + m - 1 - (idx / n);
}

#define M 5
#define N 7

int main()
{
        size_t i, j;
        T a[M][N];

        for (i = 0; i < M; ++i)
                for (j = 0; j < N; ++j)
                        a[i][j] = i * N + j;

        rotate(&a[0][0], M, N, turn_ccw);
        dump(N, M, (T (*)[M])&a[0][0]);
        printf("\n");
        rotate(&a[0][0], N, M, turn_cw);
        dump(M, N, (T (*)[N])&a[0][0]);
}

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

Потому что скорость выполнения зависит от частоты и типа процессора, а в наше время и от количества ядер/процессоров (потоков).