Cod sursa(job #2207738)

Utilizator Simon2712Simon Slanina Simon2712 Data 26 mai 2018 16:45:02
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 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,cap1=801,cap2;
  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++)
    {
      cap1=801;
      y=v[j];
      st=j+1;
      dr=n;
      while(st<=dr)
      {
        mij=(st+dr)/2;
        if(x+y<v[mij])
          dr=mij-1;
        else
        {
          st=mij+1;
          if(x+v[mij]>=y && y+v[mij]>=x)
            if(mij<cap1)
            cap1=mij;
        }
      }
      if(cap1!=801)
      {
          st=j+1;
          dr=n;
          cap2=0;
          while(st<=dr){
            mij=(st+dr)/2;
            if(x+v[mij]<y || y+v[mij]<x)
              st=mij+1;
            else
            {
                dr=mij-1;
                if(x+y>=v[mij])
                  if(mij>cap2)
                    cap2=mij;
            }
          }
          cnt+=cap2-cap1+1;
      }
    }
  }
  printf("%d",cnt);
  return 0;
}