Cod sursa(job #1106119)

Utilizator MoneaVladMonea Vlad MoneaVlad Data 12 februarie 2014 15:42:15
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int nr, i, j, k, sol, q, x[1111], y[1111];
long double p[5000005], aux[5000005];


void interclasare (int a, int b, int c)
{
    int poz1 = a;
    int poz2 = b;
    int z = 1;
    while ( poz1 <= b || poz2 <= c)
    {
        if (p[poz1] <= p[poz2])
        {
            aux[z] = p[poz1];
            z++;
            poz1++;
        }
        else
        {
            aux[z] = p[poz2];
            z++;
            poz2++;
        }
    }
    while (poz1 <= b)
    {
       aux[z] = p[poz1];
            z++;
            poz1++;
    }
    while (poz2 <= c)
    {
       aux[z] = p[poz2];
            z++;
            poz2++;
    }
    for (int i = 1; i < z; i++)
    {
        p[a] = aux[i];
        a++;
        aux[i] = 0;
    }
}

void sortare (int start, int fin)
{
    if (start == fin)
        return;
    int mid = start + (fin - start) / 2;
    sortare(start, mid);
    sortare(mid, fin);
    interclasare(start, mid, fin);
}


int main()
{
    in >> nr;
    for (i = 1; i <= nr; i++)
    {
        in >> x[i] >> y[i];
    }
    k = 0;
    for (i = 1; i < nr; i++)
        for (j = i + 1; j <= nr; j++)
        {
            k++;
            if (x[i] == x[j])
                p[k] = 2222222;
            else
                p[k] = (double)(y[j] - y[i])/(x[j] - x[i]);
        }
    sortare(1, k);
    q = 1;
    for (i = 1; i < k; i++)
        for (j = i + 1; j <= k; j++)
        {
            if (p[i] == p[j])
                q++;
            else
            {
                sol += q * (q - 1) / 2;
                q = 1;
            }
        }
    out << sol << "\n";
    in.close();
    out.close();
    return 0;
}