Cod sursa(job #1969997)

Utilizator darian2001Clodnischi Darian Antonio darian2001 Data 18 aprilie 2017 19:41:22
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

int n;
vector <short> bat;
int triunghiuri;

short regula1(short i,short j){
    short left=i,right=j,mid;
    while(left<=right){
        mid=(left+right)/2;
        if(bat[mid]<bat[j]-bat[i]){
            left=mid+1;
        }
        else if(bat[mid]>=bat[j]-bat[i]){
            right=mid-1;
        }
    }
    return left;
}
short regula2(short i,short j){
    short left=i,right=j,mid;
    while(left<=right){
        mid=(left+right)/2;
        if(bat[mid]>bat[j]+bat[i])
            right=mid-1;
        else left=mid+1;
    }
    return right;
}
short caut(short i,short j){
    return regula2(i,j)-regula1(i,j);
}

int main(){
    f>>n;
    for(short i=1,lungime;i<=n;i++)
        f>>lungime,bat.push_back(lungime);
    sort(bat.begin(),bat.end());
    for(short i=0;i<n-3;i++){
        for(short j=n-1;j>=i+2;j--)
            triunghiuri+=caut(i,j);
    }
    g<<triunghiuri;

    f.close();
    g.close();
}