Cod sursa(job #1362611)

Utilizator j.loves_rockJessica Joanne Patrascu j.loves_rock Data 26 februarie 2015 13:58:37
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <climits>
#include <algorithm>

#define eps 1e-12
using namespace std;
struct da {int x,y;};

da a[1500];
int n,i,NR,j,nr;

long long sol;

double v[1000005];

int main()
{
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);
    scanf("%d",&n);
    for (i = 1; i <= n; i++)
        scanf("%d %d\n",&a[i].x,&a[i].y);
    for (i = 1; i <= n; i++)
        for (j = i + 1; j <= n; j++)
            if (a[i].x - a[j].x != 0) v[++nr] = (double)(a[i].y - a[j].y) / (a[i].x - a[j].x);
                    else v[++nr]=INT_MAX;

    sort(v + 1,v + nr + 1);
    i = 2;
    while (i <= nr)
    {
        NR =  1;
        while (v[i] - v[i-1] < eps && v[i] - v[i-1] > -eps)
        {
            i++;
            NR++;
        }
        sol += 1LL * NR * (NR - 1) / 2;
        if (NR == 1) i++;
    }
    printf("%lld\n",sol);
    return 0;
}