Cod sursa(job #2091898)

Utilizator calin1Serban Calin calin1 Data 20 decembrie 2017 15:35:06
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 1005

using namespace std;

long long n, nr, numitor_0;

struct rational
{
    long long numarator, numitor;
};

rational pante[N];

struct coord
{
    long long x, y;
};

coord vec[N];

rational calc_panta(long long x1, long long y1, long long x2, long long y2)
{
    rational tmp;

    tmp.numarator = y2 - y1;
    tmp.numitor = x2 - x1;

    return tmp;

}

long long cmp(rational a, rational b)
{
    return(a.numarator * b.numitor < a.numitor * b.numarator);
}

void solve()
{
    long long l_pante = 0;

    for(long long i = 0 ; i < n - 1 ; ++i)
    {
        for(long long j = i + 1 ; j < n ; ++j)
        {
            pante[l_pante++] = calc_panta(vec[i].x, vec[i].y, vec[j].x, vec[j].y);

            if(!pante[l_pante - 1].numitor)
            {
                l_pante--;

                numitor_0++;
            }
        }
    }

    sort(pante, pante + l_pante, cmp);

    for(int i = 0 ; i < l_pante - 1 ; ++i)
    {
        if(!cmp(pante[i], pante[i + 1]))
        {
            nr++;
        }
    }

    printf("%d",nr + numitor_0 * (numitor_0 - 1) / 2);
}

void read()
{
    scanf("%d", &n);

    for(int i = 0 ; i < n ; ++i)
    {
        scanf("%d %d\n", &vec[i].x, &vec[i].y);
    }

    solve();
}

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

    read();

    return 0;
}