Cod sursa(job #1197609)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 12 iunie 2014 22:11:49
Problema Numarare triunghiuri Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <stdio.h>
#include <stdlib.h>
int v[2000];
int compar(const void * a, const void * b) {
  return ( *(int*)a - *(int*)b );
}
int main()
{   FILE*fi,*fout;
    int n,i,j,min,max,st,dr,mij,pozmin,pozmax;
    long long nr,con;
    fi=fopen("nrtri.in" ,"r");
    fout=fopen("nrtri.out" ,"w");
    fscanf(fi,"%d" ,&n);
    for(i=0;i<n;i++)
      fscanf(fi,"%d" ,&v[i]);
    qsort( v, n, sizeof(int), compar );
    nr=0;
    for(i=0;i<n-1;i++){
        for(j=i+1;j<n;j++){
            if(i!=j){
                 if(v[i]>v[j]){
                     min=v[i]-v[j]+1;
                     max=v[i]+v[j]-1;
                 }
                 else{
                     min=v[j]-v[i]+1;
                     max=v[i]+v[j]-1;
                 }
                 st=0;
                 dr=n;
                 while(dr-st>1){
                     mij=(st+dr)/2;
                     if(v[mij]>min)
                       dr=mij;
                     else
                       st=mij;
                 }
                 while(mij>=0&&v[mij]>=min)
                   mij--;
                 mij++;
                 pozmin=mij;
                 st=0;
                 dr=n;
                 while(dr-st>1){
                     mij=(st+dr)/2;
                     if(v[mij]>max)
                       dr=mij;
                     else
                       st=mij;
                 }
                 while(mij<n&&v[mij]<=max)
                  mij++;
                 mij--;
                 pozmax=mij;
                 con=pozmax-pozmin+1;
                 if(con>0){
                    if(i>=pozmin&&i<=pozmax)
                      con--;
                    if(j>=pozmin&&j<=pozmax)
                      con--;
                 }
                 nr=nr+con;
            }
        }
    }
    fprintf(fout,"%lld" ,nr/3);
    fclose(fi);
    fclose(fout);
    return 0;
}