Cod sursa(job #1361015)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 25 februarie 2015 19:11:14
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <algorithm>

#define f first
#define s second
#define mp make_pair

using namespace std;

int a[1024], b[1024];
pair <int, int> v[3000010];

bool cmp (pair <int, int> a, pair <int, int> b)
{
    long long x = 1LL * a.f * b.s;
    long long y = 1LL * b.f * a.s;
    return (x < y);
}

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

    int n;
    scanf ("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf ("%d %d", &a[i], &b[i]);

    int k = 0;
    for (int i = 1; i < n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (a[i] - a[j]) v[++k] = mp (b[i] - b[j], a[i] - a[j]);

    sort (v + 1, v + k + 1, cmp);

    //for (int i = 1; i <= k; ++i)
      //  printf ("%lf\n", 1.0 * v[i].f / v[i].s);

    int i = 2;
    long long nr = 0LL;
    while (i <= k)
    {
        long long nrr = 1LL;
        long long x = 1LL * v[i - 1].f * v[i].s;
        long long y = 1LL * v[i].f * v[i - 1].s;


        while (x == y)
        {
            ++nrr;
            ++i;

            x = 1LL * v[i - 1].f * v[i].s;
            y = 1LL * v[i].f * v[i - 1].s;
        }

        nr += 1LL * nrr * (nrr - 1) / 2;
        ++i;
    }

    printf ("%lld\n", nr);

    return 0;
}