Решение задачи Двойная решетка с Меньшиков

Без пояснения   Просмотров: 31


Две бесконечные равномерные прямоугольные решётки заданы размерами ячеек x1 y1 и x2 y2. Решётки расположены на плоскости параллельно друг другу и координатным осям так, что смещение одного из узлов второй решётки относительно узла первой составляет Dx по горизонтали и Dy по вертикали. В результате наложения образуется новая, "составная" решётка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решётки.

Ограничения: 1 <= x1, y1, x2, y2 <= 100, 0 <= Dx < x1, 0 <= Dy < y1, все числа целые.

Код

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
 
using namespace std;
 
int x1,y1,x2,y2,dx,dy;
void input()
{
    cin>>x1>>y1>>x2>>y2>>dx>>dy;
}
int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}
int lcm(int a, int b)
{
    return  (a*b)/gcd(a,b);
}
void output(set<int> &S)
{
    printf("%d\n",S.size());
    for (set<int>::iterator it = S.begin(); it != S.end(); it++)
        printf("%d\n",*it);
}
void solve()
{
    int maxX = dx + lcm(x1, x2);
    int maxY = dy + lcm(y1, y2);
    vector<int> X, Y;
    set<int> S;
 
    for (int x = 0; x<=maxX; x+=x1)
        X.push_back(x);
    for (int x = dx; x<=maxX; x+= x2)
        X.push_back(x);
   
 
    for (int y = 0; y<=maxY; y+=y1)
        Y.push_back(y);
    for (int y = dy; y<=maxY; y+=y2)
        Y.push_back(y);
 
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    int dx, dy;
    for (int i = 0; i < X.size()-1; i++) {
        for (int j = 0; j < Y.size()- 1; j++) {
            dx = X[i+1] - X[i];
            dy = Y[j+1] - Y[j];
            S.insert(dx*dy);
        }
    }
    S.erase(0);
    output(S);
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться