Cod sursa(job #2207080)

Utilizator Simon2712Simon Slanina Simon2712 Data 24 mai 2018 20:45:23
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;
int v[801];
int main()
{
  freopen("nrtri.in","r",stdin);
  freopen("nrtri.out","w",stdout);
  int n,mij,st,dr,i,y,x,cnt=0,j;
  scanf("%d",&n);
  for(i=1;i<=n;i++)
    scanf("%d",&v[i]);
  sort(v+1,v+n+1);
  for(i=1;i<n-1;i++)
  {
    x=v[i];
    for(j=i+1;j<n;j++)
    {
      y=v[j];
      st=j+1;
      dr=n;
      while(st<=dr)
      {
        mij=(st+dr)/2;
        if(x+y<v[mij])
          dr=mij-1;
        else
        if(x+v[mij]<y || y+v[mij]<x)
          st=mij+1;
        else
        {
          cnt++;
          if(st==dr)
            st=dr+1;
          else
            st=mij+1;
        }
      }
    }
  }
  printf("%d",cnt);
  return 0;
}