Cod sursa(job #1151705)

Utilizator swim406Teudan Adina swim406 Data 24 martie 2014 12:23:59
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 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.p2 < y.p2) return 1;
    return 0;
}

bool cm (double a, double b) {
    return a < b;
}

double v[MMAX];

int main() {
    int N, i, j, a, b, a1, b1, vert = 0, oriz = 0, sol = 0, temp;
    double pt;
    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;
            */
            if (a != 0) {
                if (b == 0) ++oriz;
                else {
                    pt = b/(double)a;
                    v[++count] = pt;
                }
            }
            if (a == 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;
        }
    }*/
    sort (v, v + count, cm);
    temp = 1;
    for (i = 1; i < count; ++i) {
        if (v[i] == v[i-1])
            ++temp;
        else {
            sol += temp*(temp-1)/2;
            temp = 1;
        }

    }
    sol += vert*(vert-1)/2;
    sol += oriz*(oriz-1)/2;
    printf ("%d", sol);
    return 0;
}