Cod sursa(job #1697037)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 30 aprilie 2016 16:26:07
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <stdlib.h>

int x[1000], y[1000];
double v[1000000];

void myqsort(int begin, int end){
    int b=begin, e=end;
    double pivot=v[(b+e)/2];
    while(b<=e){
        while(v[b]<pivot) b++;
        while(v[e]>pivot) e--;
        if(b<=e){
            double aux=v[b];
            v[b++]=v[e];
            v[e--]=aux;
        }
    }
    if(b<end) myqsort(b, end);
    if(begin<e) myqsort(begin, e);
}

int main(){
    int n, i, j;
    FILE*fi,*fo;
    fi=fopen("trapez.in","r");
    fo=fopen("trapez.out","w");
    fscanf(fi,"%d", &n);
    for(i=0;i<n;i++)
        fscanf(fi,"%d%d", &x[i], &y[i]);
    int ind=0;
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++){
            if(x[i]!=x[j])
                v[ind++]=1.0*(y[j]-y[i])/(x[i]-x[j]);
            else
                v[ind++]=2000000000.0;
        }
    myqsort(0, ind-1);
    int l=1;
    long long s=0LL;
    for(i=1;i<ind;i++)
        if(v[i]-v[i-1]<0.0000000000000001 && v[i]-v[i-1]>-0.0000000000000001)
            l++;
        else{
            s+=l*(l-1)/2;
            l=1;
        }
    s+=l*(l-1)/2;
    fprintf(fo,"%lld", s);
    fclose(fi);
    fclose(fo);
    return 0;
}