Cod sursa(job #2222576)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 17 iulie 2018 13:22:41
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <iostream>
#include <fstream>
using namespace std;
int v[100001];
void qSort(int v[100001],int st,int dr){
int minim,maxim,temp,mijl;
maxim=dr;minim=st;
mijl=v[minim+(maxim-minim)/2];
do
{
    while(v[minim]<mijl) minim++;
    while(v[maxim]>mijl) maxim--;
    if(minim<=maxim){
        temp=v[minim];
        v[minim++]=v[maxim];
        v[maxim--]=temp;}
}while (minim<=maxim);
if(st<maxim) qSort(v,st,maxim);
if(minim<dr) qSort(v,minim,dr);
}
int main () {
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");
    int n,i,j,k,nr=0;
    f>>n;
    for(i=0;i<n;i++) f>>v[i];
    qSort(v,0,n-1);
    for(i=0;i<n-2;i++)
        for(j=i+1;j<n-1;j++)
    {   k=j+1;
        while(k<n&&v[k]<=v[i]+v[j]) {nr++;k++;}}
   g<<nr;
    return 0;}