Cod sursa(job #1814485)

Utilizator crazylamaRiclea Andrei crazylama Data 24 noiembrie 2016 08:32:08
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;

ifstream f("trapez.in");
ofstream g("trapez.out");

struct Punct {
    int x, y;
};

struct Dreapta {
    Punct A, B;
    double panta, lungime;
};

double AflaPanta(Dreapta D)
{
    /*if (D.B.x - D.A.x == 0)
        return 0;*/
    return (double)(D.B.y - D.A.y) / (double)(D.B.x - D.A.x);
}

double AflaLungimea(Dreapta D)
{
    return sqrt((D.B.x - D.A.x) * (D.B.x - D.A.x) + (D.B.y - D.A.y) * (D.B.y - D.A.y));
}

bool PuncteIdentice(Dreapta D1, Dreapta D2)
{
    if (D1.A.x == D2.A.x && D1.A.y == D2.A.y)
        return true;
    if (D1.A.x == D2.B.x && D1.A.y == D2.B.y)
        return true;
    if (D1.B.x == D2.A.x && D1.B.y == D2.A.y)
        return true;
    if (D1.B.x == D2.B.x && D1.B.y == D2.B.y)
        return true;
    return false;
}

void QuickSort(int st, int dr, vector<Dreapta> &v)
{
    if (st < dr)
    {
        int i = st, j = dr;
        Dreapta x = v[st];
        while (i < j)
        {
            while (i < j && v[j].panta >= x.panta)
                j--;
            v[i] = v[j];
            while (i < j && v[i].panta <= x.panta)
                i++;
            v[j] = v[i];
        }
        v[i] = x;
        QuickSort(st, i - 1, v);
        QuickSort(i + 1, dr, v);
    }
}

int main()
{
    int n, k = 0;
    f >> n;
    vector<Dreapta> v;
    vector<Punct> p;
    v.resize(n * (n - 1) / 2 + 1);
    p.resize(n);
    for (int i = 0; i < n; ++i)
        f >> p[i].x >> p[i].y;
    f.close();
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
        {
            v[k].A = p[i];
            v[k].B = p[j];
            v[k].panta = AflaPanta(v[k]);
            v[k].lungime = AflaLungimea(v[k]);
            ++k;
        }
    int nr = 1, nrpara = 1;
    long long sol = 0;
    QuickSort(0, k - 1, v);
    for (int i = 1; i < k; ++i)
    {
        if (abs(v[i].panta - v[i - 1].panta) <= 0.01)
        {
            /*if (!PuncteIdentice(v[i], v[i - 1]) && abs(v[i].lungime - v[i - 1].lungime) <= 0.01)
                ++nrpara;*/
            if (!PuncteIdentice(v[i], v[i - 1]))
                ++nr;
        }
        else
        {
            sol += nr * (nr - 1) / 2;
            /*sol += nrpara * (nrpara - 1);*/
            nr = 1;
            //nrpara = 1;
        }
    }
    g << nr;
    g.close();
    return 0;
}