Cod sursa(job #1104076)

Utilizator swim406Teudan Adina swim406 Data 10 februarie 2014 13:58:52
Problema Trapez Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <stdio.h>
#define NMAX 1001
#define MMAX 500000
#include <algorithm>

using namespace std;

struct dbl {
    int p1, p2;
} p[MMAX];

bool cmp (dbl x, dbl y) {
    if (x.p1 < y.p1) return 1;
    if (x.p1 > y.p1) return 0;
    if (x.p1 == y.p1) {
        if (x.p2 < y.p2) return 1;
        return 0;
    }
}

int main() {
    int N, i, j, a, b, a1, b1, vert = 0, oriz = 0, sol = 0, temp;
    int x[NMAX], y[NMAX];
    freopen ("trapez.in", "r", stdin);
    freopen ("trapez.out", "w", stdout);
    scanf ("%d", &N);
    for (i = 1; i <= N; ++i)
        scanf ("%d %d", &x[i], &y[i]);
    int count = -1;
    for (i = 1; i < N; ++i)
        for (j = i + 1; j <= N; ++j) {
            a = x[i] - x[j];
            b = y[i] - y[j];
            a1 = a, b1 = b;
            if (a1 < 0) a1 *= -1;
            if (b1 < 0) b1 *= -1;
            while (a1 != b1 && a1 != 0 && b1 != 0) {
                if (a1 < b1)
                    b1 -= a1;
                else
                    a1 -= b1;
            }
            if (a1 != 0 && b1 != 0) {
                a /= a1, b /= b1;
                if (a <= 0) a *= -1, b *= -1;
                p[++count].p1 = a;
                p[count].p2 = b;
            }
            if (a == 0) ++oriz;
            if (b == 0) ++vert;
        }
    sort (p, p+count, cmp);
    temp = 1;
    for (i = 1; i < count; ++i) {
        if (p[i].p1 == p[i-1].p1 && p[i].p2 == p[i-1].p2)
            ++temp;
        else {
            sol += temp*(temp-1)/2;
            temp = 1;
        }
    }
    sol += vert*(vert-1)/2;
    sol += oriz*(oriz-1)/2;
    printf ("%d", sol);
    return 0;
}