Wataru

Или

Одно из решений. Пусть сектор 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 переставляет одну цепочку.

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