Cod sursa(job #2560345)

Utilizator vasiliumirunamariaVasiliu Miruna-Maria vasiliumirunamaria Data 27 februarie 2020 21:56:03
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#define N 801
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n;
int a[N];

void Citire()
{
    int i;
    fin >> n;
    for(i = 1; i <= n; i++)
        fin>>a[i];
}
void Interclasare(int s, int m, int d)
{
    int i, j, k, b[801];
    i=s; j=m+1; k=0;
    while(i <= m && j <= d)
      if(a[i] < a[j]) b[++k]=a[i++];
      else b[++k]=a[j++];
    while(i <= m) b[++k]=a[i++];
    while(j <= d) b[++k]=a[j++];
    for(i = s,j = 1;i <= d; i++,j++) a[i]=b[j];

}
void MergeSort(int s, int d)
{
    if(s < d)
    {
        int m=s+(d-s)/2;
        MergeSort(s, m);
        MergeSort(m+1, d);
        Interclasare(s, m, d);
    }
}

int Cauta(int x, int y, int s, int d)
{
    int m, ct = 0;
    while(s <= d)
    {
        m=s+(d-s)/2;
        if(a[m] + x > y && a[m] + y >x && x + y > a[m])
            return n-m+1;
        else s=m+1;

    }
    return 0;

}
int main()
{
    int ct=0, i, j;
    Citire();
    MergeSort(1, n);
    //for(i = 1; i <= n ; i++)
      // fout<<a[i]<<" ";
    for(i = 1; i < n-1; i++)
      for(j = i+1; j <= n-1; j++)
        ct+=Cauta(a[i], a[j], j+1, n);
   fout<<ct;
    return 0;
}