Cod sursa(job #1765757)

Utilizator radu9876Radu Sirghe radu9876 Data 26 septembrie 2016 22:57:15
Problema Trapez Scor 60
Compilator c Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <stdio.h>
#include <stdlib.h>

int main()
{
    FILE *in, *out;
    in=fopen("trapez.in", "r");
    out=fopen("trapez.out", "w");
    int n;
    fscanf(in, "%d", &n);
    int i,j, k=0, t=0, x[n], y[n];
    long long p[n*(n-1)/2];// a[n*n], b[n*n];
    for(i=0;i<n;i++) fscanf(in, "%d %d", &x[i], &y[i]);
    for(i=0;i<n;i++)
        for(j=0;j<i;j++){
            //a[n*i+j]=x[i]-x[j];
            //b[n*i+j]=y[i]-y[j];
            p[k]=(x[i]==x[j])?10000000000LL
                :2000000000LL*(y[i]-y[j])/(x[i]-x[j]);
            k++;
        }
    //bula(k, p);
    squick(p,0,k);
    int eg=0;
    for(i=0;i<k-1;i++){
        while(i<k-1 && p[i]==p[i+1]) {eg++; i++;}
        if(eg) {
            t=t+eg*(eg+1)/2;
            eg=0;
        }
    }
    fprintf(out, "%d", t);
    return 0;
}

void bula(int n, long long p[]){
    int ok=1, i;
    while(ok){
        ok=0;
        for(i=0;i<n-1;i++) if(p[i]>p[i+1]){
            long long m=p[i];
            p[i]=p[i+1];
            p[i+1]=m;
            ok=1;
        }
    }
}

void sch(long long p[], int a, int b){
    long long m=p[a];
    p[a]=p[b];
    p[b]=m;
}

void squick(long long p[],int jos,int sus){
    if(jos+1>=sus) return;
    if(jos+2==sus){
        if(p[jos]>p[jos+1]) sch(p, jos, jos+1);
        return;
    }
    int piv=(sus+jos)/2;
    int i,j=0;
    for(i=jos;i<piv-j;i++)
        if(p[i]>p[piv]){
            j++;
            if(i<piv-j) {sch(p, i, piv-j); i--;}
        }
    sch(p,piv, piv-j);
    piv=piv-j;
    j=0;
    for(i=sus-1;i>piv+j;i--)
        if(p[i]<p[piv]){
            j++;
            if(i>piv+j) {sch(p, i, piv+j); i++;}
        }
    sch(p,piv, piv+j);
    piv=piv+j;
    squick(p,jos,piv);
    squick(p,piv+1,sus);
}

/*void sjuma(int n, double p[], int s){
    sjuma(n/2, p, s);
    sjuma(n-n/2,p, s+n/2);

}*/