Cod sursa(job #1135536)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 7 martie 2014 23:13:11
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

typedef pair<int, int> Punct;
typedef pair<Punct, Punct> Chestie;

Chestie A[500001];

Punct P[1001];

bool cmp(Chestie X, Chestie Y)
{
    return (X.first.second - X.second.second)*(Y.first.first - Y.second.first) < (Y.first.second - Y.second.second) * (X.first.first - X.second.first );
}


int main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>P[i].first>>P[i].second;
    int k = 0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            A[++k] = make_pair(P[i],P[j]);
        }
    sort(A+1,A+1+k,cmp);



    unsigned long long sol = 0;
    for(int i=1;i<=k;i++)
    {

        int d = 1;
        while(
              (A[i].first.second - A[i].second.second)*(A[i+d].first.first - A[i+d].second.first) ==
              (A[i+d].first.second - A[i+d].second.second) * (A[i].first.first - A[i].second.first)
                && i+d<=k
              )
                d++;
        d--;
        sol += (d+1)*d/2;
        i = i + d;
    }

    fout<<sol;

    fin.close();
    fout.close();
    return 0;
}