Cod sursa(job #1695314)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 26 aprilie 2016 21:35:50
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <stdlib.h>

int v[801];

void myqsort(int begin, int end){
    int b=begin, e=end, pivot=v[(b+e)/2];
    while(b<=e){
        while(v[b]<pivot) b++;
        while(v[e]>pivot) e--;
        if(b<=e){
            int aux=v[b];
            v[b++]=v[e];
            v[e--]=aux;
        }
    }
    if(b<end) myqsort(b, end);
    if(begin<e) myqsort(begin, e);
}

int main(){
    int n, i, j;
    FILE*fi,*fo;
    fi=fopen("nrtri.in","r");
    fo=fopen("nrtri.out","w");
    fscanf(fi,"%d", &n);
    for(i=0;i<n;i++)
        fscanf(fi,"%d", &v[i]);
    myqsort(0, n-1);
    long long sol=0;
    for(i=0;i<n-2;i++)
        for(j=i+1;j<n-1;j++){
            if(v[i]+v[j]>=v[j+1]){
                int st=j+1, dr=n-1;
                while(dr-st>1){
                    int m=(dr+st)/2;
                    if(v[m]>v[i]+v[j])
                        dr=m-1;
                    else
                        st=m;
                }
                if(v[dr]<=v[i]+v[j])
                    sol+=dr-j;
                else
                    sol+=st-j;
            }
            //printf("%d %d %lld\n", i, j, sol);
        }
    fprintf(fo,"%lld", sol);
    fclose(fi);
    fclose(fo);
    return 0;
}