Cod sursa(job #915033)

Utilizator PatrikStepan Patrik Patrik Data 14 martie 2013 17:56:57
Problema Trapez Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define MAX 1001
    struct punct
    {
        int x , y;
    }P[MAX];
    struct panta
    {
        int nr , num ;
    }M[MAX*MAX];
    int N , k ;
    bool comp(panta A , panta B)
    {
        bool r = A.nr*B.num < A.num*B.nr;
        if(A.nr < 0) r = !r;
        if(B.nr < 0) r = !r;
        return r;
    }
    long sol;

    void citire();
    void solve();
    void tipar();

    int main()
    {
        citire();
        solve();
        tipar();
        return 0;
    }

    void citire()
    {
        freopen("trapez.in" , "r" , stdin );
        scanf("%d" , &N);
        for( int i = 1 ; i <= N ; ++i )
            scanf("%d%d" , &P[i].x , &P[i].y);
    }

    void solve()
    {
        for( int i = 1 ; i< N ; ++i )
            for( int j = i+1 ; j <= N ; ++j )
            {
                M[++k].nr  = P[i].y-P[j].y;
                M[k].num = P[i].x-P[j].x;
            }
        sort(M+1,M+k+1,comp);
        int p =1;
        for(int i = 2 ; i <= k ; ++i )
        {
            if(1ll*(M[i-1].nr*M[i].num) == 1ll*(M[i-1].num * M[i].nr))p++;
            else
            {
                sol+=p*(p-1)/2;
                p = 1;
            }
        }
        sol+=p*(p-1)/2;
    }

    void tipar()
    {
        freopen("trapez.out" , "w" , stdout );
        printf("%ld\n" , sol);
    }