Cod sursa(job #1970033)

Utilizator darian2001Clodnischi Darian Antonio darian2001 Data 18 aprilie 2017 20:20:20
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 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=0;

short regula1(short i,short j){
    short left=i+1,right=j-1,mid,poz=-1;
    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,poz=mid;
        }
    }
    return poz;

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

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-2;i++){
        for(short j=i+2;j<n;j++)
            caut(i,j);
    }
    g<<triunghiuri;

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