Pagini recente » Cod sursa (job #2319974) | Cod sursa (job #1544841) | Cod sursa (job #2457095) | Cod sursa (job #1370135) | Cod sursa (job #2001388)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 800
#define usi unsigned short int
int v[NMAX], log=1, n;
FILE *fin, *fout;
int piv(int inf, int sup){
int st=inf, dr=sup, pivot=v[inf];
while(st<dr){
while(st<dr && pivot<=v[dr])
dr--;
v[st]=v[dr];
while(st<dr && v[st]<=pivot)
st++;
v[dr]=v[st];
}
v[st]=pivot;
return st;
}
void quick(int inf, int sup){
int m=piv(inf, sup);
if(m-1>inf)
quick(inf, m-1);
if(m+1<sup)
quick(m+1, sup);
}
int cautare(int x){
int lg=log, i;
for(i=0; lg>0; lg>>=1)
if(i+lg<n && v[i+lg]<=x)
i+=lg;
return i;
}
int main(){
fin=fopen("nrtri.in", "r");
fout=fopen("nrtri.out", "w");
int i, j, l, u, c=0, cc=0;
fscanf(fin, "%d", &n);
for(i=0; i<n; i++)
fscanf(fin, "%d", &v[i]);
quick(0, n-1);
///avem triunghiul cu laturi a, b, c
///daca stim valorile a si b, a<=b
/// b-a+1 <= c <= a+b-1
///cautam binar in vector aceste valori(lower si upper bound)
///si returnam nr de elem intre lower si upper-2(scadem pe a si b)
while(log<n)
log<<=1;
for(i=0; i<n-2; i++)
for(j=i+1; j<n-1; j++){
u=cautare(v[i]+v[j]);
c+=u-j;
cc=c;
}
fprintf(fout, "%d", c);
fclose(fin);
fclose(fout);
return 0;
}