Cod sursa(job #307308)

Utilizator gabor_oliviu1991gaboru corupt gabor_oliviu1991 Data 23 aprilie 2009 22:00:54
Problema Numarare triunghiuri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
#define N 100
using namespace std;
int search(int x, int poz);
int sir[N], n;
int main() {
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");
    int i, j, tri = 0;
    f>>n;
    for(i = 1; i <= n; i++)
          f>>sir[i];
    sort(sir+1, sir+n+1);
    for(i = 1; i < n; i++)
          for(j = i+1; j <= n; j++)
                tri+=search(sir[i]+sir[j], j+1);
    g<<tri;
    return 0;
}
int search(int x, int poz){
    int start = poz, finish = n, middle;
    while(start <= finish) {
         middle=(start+finish)/2;
         if(sir[middle] <= x && (sir[middle+1] > x || middle == n))
                        return middle-poz+1;
         else
             if(sir[middle] < x)
                 start = middle +1;
             else                 
                 finish = middle -1; }
     return 0;
}