Cod sursa(job #993037)

Utilizator SRaduRadu Szasz SRadu Data 3 septembrie 2013 02:01:33
Problema Dreptunghiuri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 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();
}

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

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

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

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

bool isXInteger(LINE L, 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) + dx;
                    if(X >= M) break;
                    sol += 1LL * (Y + 1) * (M - X);
                }
            }
        }
}

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

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