Cod sursa(job #1295067)

Utilizator RaduVisanRadu Visan RaduVisan Data 18 decembrie 2014 19:10:17
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int NMAX = 1010;

int N, X[NMAX], Y[NMAX], Ans, K;

struct Slope
{
    int DX, DY;
}S[NMAX * NMAX];

struct Comp
{
    bool operator() (const Slope &A, const Slope &B) const
    {
        int AX = A.DX, AY = A.DY, BX = B.DX, BY = B.DY, SignA, SignB;

        if(AX < 0 && AY < 0) SignA = 1;
        else if(AX < 0 || AY < 0) SignA = -1;
        else SignA = 1;

        if(BX < 0 && BY < 0) SignB = 1;
        else if(BX < 0 || BY < 0) SignB = -1;
        else SignB = 1;

        AX = abs(AX); AY = abs(AY), BX = abs(BX), BY = abs(BY);

        if(SignA == -1 && SignB == -1) return 1LL * BY * AX < 1LL * BX * AY;
        else if(SignA == -1 && SignB == 1) return 1;
        else if(SignA == 1 && SignB == -1) return 0;
        else return 1LL * AY * BX < 1LL * AX * BY;
    }
};

int main()
{
    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i)
        scanf("%i %i", &X[i], &Y[i]);

    for(int i = 1; i <= N; ++ i)
        for(int j = i + 1; j <= N; ++ j)
            S[++ K].DX = X[j] - X[i], S[K].DY = Y[j] - Y[i];

    sort(S + 1, S + K + 1, Comp());

    S[0].DX = S[1].DX - 1;
    S[0].DY = S[1].DY;

    int CntEqual = 0;
    for(int i = 1; i <= K; ++ i)
        if(1LL * S[i - 1].DY * S[i].DX == 1LL * S[i - 1].DX * S[i].DY)
            CntEqual ++;
        else
        {
            Ans += (CntEqual * (CntEqual - 1)) / 2;
            CntEqual = 1;
        }

    Ans += (CntEqual * (CntEqual - 1)) / 2;

    printf("%i\n", Ans);
}