Cod sursa(job #1288778)

Utilizator Mihai_BogdanDumitru Mihai Mihai_Bogdan Data 9 decembrie 2014 05:22:46
Problema Trapez Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<cstdio>
#include<cstdlib>
#define N 1024
#define M 500502
const double eps = (double)0.000000000001;
struct trapez{int x,y;}v[N];
short int n;
double p[M];
long long num=0,dr=0;
int compar(const void  *a,const void *b)
{
    if(*(double*)a-*(double*)b>eps)
        return 1;
    if(*(double*)b-*(double*)a>eps)
        return -1;
    return 0;
}
void citire()
{
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);
    scanf("%hd",&n);
    for (short int i=1; i<=n; ++i)
        scanf("%d%d",&v[i].x,&v[i].y);
}
void gasesc()
{
    for (short int i=1; i<n; ++i)
        for (short int j=i+1; j<=n; ++j)
            if (v[i].x!=v[j].x)
                p[++num]=(double)(v[i].y-v[j].y)/(v[i].x-v[j].x);
            else
                ++dr;
    qsort(p+1,num,sizeof(p[0]),compar);
    n=num;
    num=1;
    dr=dr*(dr-1)/2;
    short int i=1;
    for ( i=1;i<n; ++i)
        if (p[i+1]-p[i]<eps)
            ++num;
        else
        {
            dr+=num*(num-1)/2;
            num=1;
        }
    dr+=num*(num-1)/2;
    printf("%lld",dr);
}
int main()
{
    citire();
    gasesc();
    return 0;
}