Cod sursa(job #1838701)

Utilizator BLz0rDospra Cristian BLz0r Data 1 ianuarie 2017 16:51:46
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <cstdlib>
#include <climits>
#include <algorithm>
using namespace std;

#define NMAX 1002
#define INF 1 << 30
#define EPS 1e-12

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

pair <int, int> v[NMAX];
double Panta[NMAX*NMAX];


//  problema se reduce la a afla numaraul de perechi de drepte paralele
int main() {

    int N, x, y, rez = 0;

    // citire
    fin >> N;

    for (int i = 1; i <= N; ++i) {
        fin >> x >> y;
        v[i] = make_pair(x, y);
    }

    // iau toate perechile de puncte
    int k = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {

            // vad panta dreptei pe care o formeaza dupa formula (p2.y - p1.y) / (p2.x - p1.x)
            double T1 = 1.0 * (v[j].second - v[i].second);
            double T2 = 1.0 * (v[j].first - v[i].first);

            if (T2 == 0) // dreapta perpendiculara
                Panta[++k] = INF;
            else
                Panta[++k] = T1 / T2;
        }
    }

    sort(Panta + 1, Panta + k + 1); //sortam pantele

    int nr = 0;
    for (int i = 1; i <= k + 1; ++i) {
        if (fabs(Panta[i] - Panta[i - 1]) < EPS) //numaram toate perechile de puncte cu aceeasi panta
            nr++;
        else {
            rez += (nr * (nr - 1)) / 2; // stim ca sunt 4 puncte distincte deoarece nu exista 3 puncte coliniare
            nr = 1;                     // aplicam Comb(N,2) pentru dreptele cu aceeasi panta
        }
    }

    //afisare
    fout << rez;

    return 0;
}