Cod sursa(job #2067972)

Utilizator ScarymovieMocanu Alexandru Scarymovie Data 16 noiembrie 2017 23:47:57
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int>v;int n,nr;
int cautbin(int left,int right,int x)
{
    int st=left,dr=right,LastApp=left-1;
    while(st<=dr)
        {
            int mij=(dr-st)/2+st;
            if(v[mij]<=x) {LastApp=mij;st=mij+1;continue;}
            if(v[mij]>x) {dr=mij-1;continue;}
        }
    return LastApp;
}
int main()
{
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");
    f>>n;v.resize(n);int i,j;
    for(i=0;i<n;++i) f>>v[i];
    sort(v.begin(),v.end());
    for(i=0;i<n;++i)
        for(j=i+1;j<n;++j)
            nr+=cautbin(j+1,n-1,v[i]+v[j])-j;
    g<<nr<<'\n';
    return 0;
}