Cod sursa(job #1397484)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 23 martie 2015 16:09:21
Problema Trapez Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#define INF 2000001050.0
#define EPS 1e-12
#define MAXN 1000
int x[MAXN], y[MAXN], n;
double v[MAXN*(MAXN+1)/2];
inline int tata(int p){
    return (p-1)/2;
}
inline int fiust(int p){
    return 2*p+1;
}
inline int fiudr(int p){
    return 2*p+2;
}
inline void swap(int a, int b){
    double aux=v[a];
    v[a]=v[b];
    v[b]=aux;
}
inline void coborare(int p){
    int q, f=1;
    while((f==1)&&(fiust(p)<n)){
        q=fiust(p);
        if((fiudr(p)<n)&&(v[fiudr(p)]>v[q])){
            q=fiudr(p);
        }
        if(v[q]>v[p]){
            swap(p, q);
            p=q;
        }else{
            f=0;
        }
    }
}
inline void heapify(){
    int i;
    for(i=tata(n-1); i>=0; i--){
        coborare(i);
    }
}
inline void heapSort(){
    int cn=n;
    while(n>1){
        n--;
        swap(0, n);
        coborare(0);
    }
    n=cn;
}
int main(){
    int k, i, j;
    long long ans;
    FILE *fin, *fout;
    fin=fopen("trapez.in", "r");
    fout=fopen("trapez.out", "w");
    fscanf(fin, "%d", &k);
    for(i=0; i<k; i++){
        fscanf(fin, "%d%d", &x[i], &y[i]);
    }
    n=0;
    for(i=0; i<k; i++){
        for(j=i+1; j<k; j++){
            if(x[i]==x[j]){
                v[n++]=INF;
            }else{
                v[n++]=(double)(y[i]-y[j])/(double)(x[i]-x[j]);
            }
        }
    }
    heapify();
    heapSort();
    ans=0;
    i=0;
    while(i<n){
        j=1;
        i++;
        while((i<n)&&(v[i]-v[i-1]<EPS)){
            j++;
            i++;
        }
        ans+=(j*(long long)(j-1))/2LL;
    }
    fprintf(fout, "%lld\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}