Cod sursa(job #993038)

Utilizator SRaduRadu Szasz SRadu Data 3 septembrie 2013 02:04:46
Problema Dreptunghiuri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <fstream>

using namespace std;

const double EPS = 1e-6;

int N, M;
long long sol;

#define x first
#define y second

struct LINE {
    double A, B, C;
    LINE(double _A, double _B, double _C) {
        A = _A, B = _B, C = _C;
    }
};

void citire() {
    ifstream in("dreptunghiuri.in");
    in >> N >> M;
    in.close();
}

inline LINE getLine(pair<int, int> P, double panta) {
    return LINE(panta, -1.0, 1.0 * P.y - panta * P.x);
}

inline double fabs(double x) {
    if(x < -EPS) return -x;
    return x;
}

inline bool EQUAL(double A, double B) {
    return fabs(A - B) < EPS;
}

inline double getX(const LINE &L, const int &y) {
    return -1.0 * (L.B * y + L.C) / L.A + EPS;
}

inline bool isXInteger(const LINE &L, const int &Y) {
    int X = getX(L, Y);
    return EQUAL(L.A * X + L.B * Y + L.C, 0.0);
}

void solve() {
    for(int dx = 1; dx < M; dx++)
        for(int dy = 1; dy < N; dy++) {
            //adaug solutiile paralele cu laturile
             sol += 1LL * (N - dy) * (M - dx);
            //adaug solutiile smenoase
            double panta = (1.0 * dy) / (1.0 * dx);
            panta = -1.0 / panta;
            LINE L = getLine(make_pair(0, N - dy - 1), panta);
            for(int Y = N - dy - 2; Y >= 0; Y--) {
                bool isInteger = isXInteger(L, Y);
                if(isInteger) {
                    int X = getX(L, Y), dY = N - dy - 1 - Y, dX = X;
                    while(X + dx < M && Y >= 0) {
                        sol += 1LL * (Y + 1) * (M - X - dx);
                        X += dX, Y -= dY;
                    } break;
                }
            }
        }
}

void afisare() {
    ofstream out("dreptunghiuri.out");
    out << sol << "\n";
    out.close();
}

int main() {
    citire();
    solve();
    afisare();
    return 0;
}