Cod sursa(job #2073321)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 22 noiembrie 2017 22:37:46
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("trapez.in");
ofstream fout("trapez.out");

pair<int, int > coord[1005], pante[1000010];
int nr_pante;
int nr;
int cmmdc(int a, int b)
{
    return b ? cmmdc(b, a % b) : a;
}

int main()
{
    int n;

    fin >> n;
    for(int i = 1; i <= n; ++i) {
        fin >> coord[i].first >> coord[i].second;

        for(int j = 1; j < i; ++j) {
            int y = coord[i].second - coord[j].second; // numaratorul pantei
            int x = coord[i].first - coord[j].first; // numitorul pantei

            if(x == 0) { // panta este infinit deci dreapta mea este verticala
                pante[++nr_pante] = make_pair(0, 0);
                continue;
            }

            int d = cmmdc(abs(x), abs(y)); // aduc fractia mea la forma ireductibila
            x /= d;
            y /= d;

            if((x < 0 and y < 0) || (x < 0 and y > 0)) {
                x *= -1;
                y *= -1;
            }

            pante[++nr_pante] = make_pair(x, y);
        }
    }

    sort(pante + 1, pante + nr_pante + 1);

    int ans = 0;
    for(int i = 1; i <= nr_pante; ++i) {
        if(pante[i] == pante[i - 1])
            nr++;
        else {
            ans += nr * (nr - 1) / 2;
            nr = 1;
        }
    }

    fout << ans;

    return 0;
}