Cod sursa(job #1522565)

Utilizator CartofJohnsonFMI Tanasescu Andrei CartofJohnson Data 11 noiembrie 2015 20:15:26
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <stdio.h>
#include <stdlib.h>
struct _{int n,x;} A[805]; int n,r;
int cmp(const void* a, const void* b){
	return ((_*)a)->x - ((_*)b)->x;
}
int main(){
	FILE* fin=fopen("nrtri.in","r");
	FILE* fout=fopen("nrtri.out","w");
	if(!fin || !fout)return 0;
	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);
	return 0;
}