Cod sursa(job #1522557)

Utilizator CartofJohnsonFMI Tanasescu Andrei CartofJohnson Data 11 noiembrie 2015 20:10:56
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <stdio.h>
#include <stdlib.h>
struct _{int n,x;} A[800]; int n,r;
int cmp(const void* a, const void* b){
	return ((_*)a)->x - ((_*)b)->x;
}
int main(){
	FILE* fin=fopen("ntri.in","r");
	FILE* fout=fopen("ntri.out","w");
	fscanf(fin,"%d",&n);
	for(register int i=0;i<n;i++)
		A[i].n=i+1,
		fscanf(fin,"%d",&(A[i].x));
	qsort(A,n,sizeof(_),cmp);
	for(register int i=0;i<n;i++){
		int k=i+2;
		for(register int j=i+1;j<n-1;j++){
			if(A[i].x+A[j].x<A[j+1].x)continue;//nem triunghiulete
			if(k<j+1)k=j+1;//altfel am sanse de dupa j
			for(;k<n-1 && A[i].x+A[j].x>=A[k+1].x;k++);
			r+=k-j;
		}
	}
	fprintf(fout,"%d",r);
}