Cod sursa(job #1494959)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 2 octombrie 2015 08:13:55
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
unsigned short int v[2001];
struct stick{unsigned short int s,t1,t2;};
stick w[2000001];
bool cmp(stick a,stick b){
    if(a.s<b.s)
        return true;
    else
        if(a.s==b.s)
            if(a.t1<a.t2)
                return true;
            else
                return false;
        else
            return false;
}
unsigned short int verif(unsigned short int a,unsigned short int b,unsigned short int c){
    if(a<b+c&&b<a+c&&c<a+b)
        return 0;
    else
        return 1;
}
unsigned short int cautbin(unsigned short int l1,unsigned short int val,unsigned short int l2){
    unsigned short int mij,rasp=l2+1;
    while(l1<=l2){
        mij=(l1+l2)/2;
        if(w[mij].s<=val){
            l1=mij+1;
        }
        else{
            l2=mij-1;
            rasp=mij;
        }
    }
    return rasp;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("nrtri.in","r");
    fout=fopen("nrtri.out","w");
    int i,j,k=0,n,cate=0;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(fin,"%hu",&v[i]);
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++){
            k++;
            w[k].s=v[i]+v[j];
            w[k].t1=i;
            w[k].t2=j;
        }
    sort(w+1,w+k+1,cmp);
    for(i=1;i<=n;i++){
        j=cautbin(1,v[i],k);
        while(j<=k){
            if(w[j].t1!=i&&w[j].t2!=i&&verif(v[i],v[w[j].t1],v[w[j].t2])==0)
                (long long)cate++;
            j++;
        }
    }
    cate/=3;
    fprintf(fout,"%d",cate);
    fclose(fin);
    fclose(fout);
return 0;
}