Cod sursa(job #887179)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 23 februarie 2013 16:28:40
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
#include <fstream>
using namespace std;
int n;
int v[1020];

void get_data(){
ifstream in("nrtr.in");

 in>>n;
 for(int i=0;i<n;i++){
    in>>v[i];
 }
}

void Merge(int start,int med,int end1)
{
    int i,j;
    int Aux[end1-start+2],poz = 0;
    for(i=start,j=med+1;i<=med||j<=end1;)
    {
        if(i<=med&&j<=end1)
            if(v[i]<=v[j])
                 Aux[poz++] = v[i++];
            else Aux[poz++] = v[j++];
        else
            if(i<=med)
                Aux[poz++] = v[i++];
            else
                Aux[poz++] = v[j++];
    }
    for(i=0;i<poz;i++)
        v[start+i] = Aux[i];
}

void MergeSort(int start,int end1)
{
    int med = (start + end1)/2;
    if(start==end1)
        return;
    else
    {
        MergeSort(start,med);
        MergeSort(med+1,end1);
        Merge(start,med,end1);
    }
}
int cauta(int poz, int start, int finish)//cea mai mare pozitie pt care v[a]+v[b]>=v[med]
{
    int med=(start+finish)/2;
    while (start<=finish){
      if (poz>=v[med]&& v[med+1]>poz) return med;
     else
     if (poz>=v[med]){
        start=med+1;
        med=(start+finish)/2;
     }else{
     finish=med-1;
     med=(start+finish)/2;
     }
    }
    return -1;
    }




int solve(){
int nr=0;
for (int a=0;a<=n-3;a++)
    for (int b=a+1;b<=n-2;b++){
        int start=b+1;
        int final1=n ;
       int c=cauta(v[a]+v[b],start,final1);
        if (c>b)
            nr+=c-b;
    }
    return nr;
}

int main(){
ofstream out("nrtr.out");
get_data();
MergeSort(0,n-1);
v[n]=11111111;
out<<solve();
return 0;
}