Compruebe si las cuerdas de un círculo son simétricas después de alguna rotación

Dados dos enteros N y M , N indica puntos equidistantes en la circunferencia de un círculo y M indica el número de cuerdas formadas con esos puntos. También se da un vector de pares C que contiene la posición de las cuerdas. La tarea es rotar el círculo en cualquier grado, digamos X, donde 0 < X ​​< 360, y verificar si las cuerdas de siguen siendo simétricas al círculo original.

Ejemplo: 

Entrada: N = 12, M = 6, C = {{1, 3}, {3, 7}, {5, 7}, {7, 11}, {9, 11}, {11, 3}};
Salida: SI

Original

Después de la rotación

Entrada: N = 10, M = 3, C = {{1, 2}, {3, 2}, {7, 2}}
Salida: NO

No es posible la simetría rotacional

Enfoque ingenuo: gire para cada distancia K en el rango [1, N ] y verifique para cada punto [a, b] si el punto girado [a + K , b + K ] existe. 
Si existe algún k, imprima SÍ; de lo contrario, imprima NO
Complejidad de tiempo : O (N * M)

Enfoque Eficiente: Basta verificar los divisores de N . 
Supongamos que si rotamos la imagen K unidades, toda la imagen se dividirá en N/K bloques. Entonces, si K no es un divisor de N , habrá un bloque asimétrico de longitud menor que K y la imagen nunca será simétrica a la figura original.
Así que calcule todos los divisores de N y verifique que para cada cuerda exista o no la cuerda rotada.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to calculate
// divisors of a number in O(sqrt(N))
vector<int> calculateDivisors(int N)
{
    vector<int> div;
    for (int i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            div.push_back(i);
            if (N / i != i && i != 1) {
                div.push_back(N / i);
            }
        }
    }
    return div;
}
int checkRotationallySymmetric(
    vector<pair<int, int> > A,
    int N, int M)
{
    // Maintain a set to check quickly
    // the presence of a chord
    set<pair<int, int> > st;
    for (int i = 0; i < M; i++) {
        --A[i].first, --A[i].second;
        if (A[i].first > A[i].second) {
            swap(A[i].first, A[i].second);
        }
        st.insert(A[i]);
    }
 
    // Calculate the divisors of N.
    vector<int> div = calculateDivisors(N);
 
    // Iterate through the divisors
    for (auto x : div) {
        bool exist = 1;
        for (int i = 0; i < M; i++) {
            int dx = (A[i].first + x) % N;
            int dy = (A[i].second + x) % N;
            if (dx > dy) {
                swap(dx, dy);
            }
            if (st.find({ dx, dy }) != st.end()) {
 
                // There exists a valid
                // chord after rotation
            }
            else {
 
                // There is no valid chord after rotation
                exist = false;
                break;
            }
        }
 
        // if there exist another chord after
        // rotation for every other chord print
        // YES and exit the function
        if (exist) {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    return 0;
}
 
// Driver Code
int main()
{
    int N = 12, M = 6;
    vector<pair<int, int> > C
        = { { 1, 3 }, { 3, 7 }, { 5, 7 },
             { 7, 11 }, { 9, 11 }, { 11, 3 } };
    checkRotationallySymmetric(C, N, M);
    return 0;
}

// JavaScript Program to for the above approach
 
// Utility function to calculate
// divisors of a number in O(sqrt(N))
function calculateDivisors(N)
{
    let div = new Array();
    for (let i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            div.push(i);
            if (Math.floor(N / i) != i && i != 1) {
                div.push(Math.floor(N / i));
            }
        }
    }
 
    return div;
}
function checkRotationallySymmetric( A, N, M)
{
    // Maintain a set to check quickly
    // the presence of a chord
    let st = new Set();
    for (let i = 0; i < M; i++) {
        A[i][0] = A[i][0] - 1;
        A[i][1] = A[i][1] - 1;
        if (A[i][0] > A[i][1]) {
            let temp = A[i][0];
            A[i][0] = A[i][1];
            A[i][1] = temp;
        }
        st.add(A[i].join(''));
    }
 
    // Calculate the di   ors of N.
    let div = calculateDivisors(N);
     
    // Iterate through the divisors
    for (let j = 0; j < div.length; j++){
         
        let exist = true;
        for (let i = 0; i < M; i++) {
            let dx = (A[i][0] + div[j]) % N;
            let dy = (A[i][1] + div[j]) % N;
            if (dx > dy) {
                 
                // swapping dx and dy.
                let temp = dx;
                dx = dy;
                dy = temp;
            }
             
            if (st.has([dx, dy].join(''))) {
                // There exists a valid
                // chord after rotation
            }
            else {
                // console.log([dx, dy]);
                // There is no valid chord after rotation
                exist = false;
                break;
            }
        }
 
        // if there exist another chord after
        // rotation for every other chord print
        // YES and exit the function
        if (exist) {
            console.log("YES");
            return 0;
        }
    }
    console.log("NO");
    return 0;
}
 
// Driver Code
let N = 12, M = 6;
let C
    = [[1, 3 ], [3, 7 ], [5, 7 ],
         [7, 11 ], [9, 11], [11, 3 ]];
checkRotationallySymmetric(C, N, M);
 
// The code is contributed by Gautam goel (gautamgoel962)

YES

Complejidad de tiempo: O(M*sqrt(N)*log M)
Complejidad de espacio: O(M)